algorithm - Floyd-Warshall 如何成为动态算法？

Question

由于 Floyd-Warshall 算法是动态的，这意味着它必须始终提供最佳解决方案，对吗？所以让我感到困惑的是，在算法的每个部分中，这些最佳解决方案的性质是什么——特别是，我试图理解以下三个问题：

• 迭代 0：在任何迭代发生之前提供什么最佳（即精确）解决方案 ？

• 迭代 1：在本次迭代结束时提供什么最佳（即精确）解决方案？

• 迭代 i（对于任意 i > 0）：在此迭代结束时提供什么最佳（即精确）解决方案？

任何人都可以阐明这些担忧吗？

Answer 1

迭代0：在任何迭代之前，获得的最优解包含无需遍历任何节点即可到达的节点。所以在第一次迭代之前你只知道一个节点到自身的距离，而一个节点到自身的距离为0。

迭代 1：在第一次迭代之后，您将获得由边直接连接的任意两个节点之间的距离。

迭代 i：在iteration i您将任意两个节点之间的距离分开不超过i边之后。

Answer 2

回想一下，外部循环迭代k，候选路径 from itoj可以经过的“中间”顶点：

for k in 0..N-1
    for i in 0..N-1
        for j in 0..N-1
            g[i,j] = min(g[i,j], g[i,k]+g[k,j])

因此，在所有迭代之前，部分解（此时相当于未修改的邻接矩阵）表示最终解的子集，其中表示所有直接从i到j的最短路径。

在一次迭代之后，通过第一个顶点（在 index 处0）的最短路径被添加到混合中。

迭代后K，部分解决方案包含最短路径，这些最短路径是 (1) 直接路径，或 (2) 通过 集合中的一个或多个顶点{0..K-1}，包括 。当然一旦K达到N，解决方案就完成了。