algorithm - Floyd-Warshall 算法是如何工作的，K 是什么？

Question

我很难理解Floyd-Warshall 算法。我知道它是如何工作的，就像我知道如何用手做一样，但我需要通过计算机感知来理解它。

FOR k <-- 1 TO N DO
    FOR i <-- 1 TO N DO
        FOR j <-- TO N DO 
            IF Djk + Dkj < DiJ THEN
                Dij <-- djk + dkj

k, iandj是迭代的变量，它迭代直到n值，我猜它是一个嵌套循环，然后它查看每个节点，然后找到最短路径？

score 4 · Accepted Answer

Floyd-Warshall 中 k 的一个大体简化的含义是图中的“路点”。最后两行可以解释如下：“如果你可以从 i 到 k，然后从 k 到 j，通过你到目前为止找到的任何路径，比从 i 到 j 更快，那么从 i 到 j 到 k 的路径变为新的最短路径”。

score 1 · Accepted Answer

K代表中间顶点。所以，外循环基本上说让第 K 个顶点作为中间停止点。内部的两个循环然后检查邻接矩阵中的每个项目，并检查使用 K 的距离（使用 K 作为中间顶点）是否小于从顶点 i 到 j 的距离（位置 i，j 在邻接矩阵）。如果距离更小，则更新 d[i,j]。

2 回答 2