en/study/algorithms/floyd-warshall-algorithm

Floyd-Warshall 算法是一种用于计算图中所有顶点对之间最短路径的算法。它适用于带权图，并且可以在多项式时间内完成计算。

算法描述

Floyd-Warshall 算法的基本思想是通过逐步增加中间顶点，逐步寻找两顶点间的最短路径。

1. 初始化一个二维数组 dist，表示图中所有顶点对之间的距离。对于任意两个顶点 i 和 j，如果 i 和 j 之间有直接路径，则 dist[i][j] 为该路径的长度；否则，dist[i][j] 为无穷大。
2. 遍历所有的顶点 k，对于每个顶点对 (i, j)，如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j]。
3. 经过上述步骤后，dist 数组中存储了图中所有顶点对之间的最短路径长度。

算法示例

假设有如下图：

A -- 1 -- B
|     / \
|    2   3
|   /     \
D -- 4 -- C

我们可以通过以下步骤计算所有顶点对之间的最短路径：

1. 初始化 dist 数组：

   dist = [
       [0, 1, ∞, ∞],
       [1, 0, 2, 3],
       [∞, 2, 0, 4],
       [∞, 3, 4, 0]
   ]
   

2. 遍历所有顶点 k：
   • 对于 k = A，更新 dist 数组：

     dist = [
         [0, 1, ∞, ∞],
         [1, 0, 2, 3],
         [∞, 2, 0, 4],
         [∞, 3, 4, 0]
     ]
     

   • 对于 k = B，更新 dist 数组：

     dist = [
         [0, 1, 1, ∞],
         [1, 0, 2, 3],
         [1, 2, 0, 4],
         [1, 3, 4, 0]
     ]
     

   • 对于 k = C，更新 dist 数组：

     dist = [
         [0, 1, 1, 2],
         [1, 0, 2, 3],
         [1, 2, 0, 4],
         [1, 3, 4, 0]
     ]
     

   • 对于 k = D，更新 dist 数组：

     dist = [
         [0, 1, 1, 2],
         [1, 0, 2, 3],
         [1, 2, 0, 4],
         [1, 3, 4, 0]
     ]
     

最终，dist 数组中存储了图中所有顶点对之间的最短路径长度。

扩展阅读

想了解更多关于算法的知识？可以阅读本站关于 算法基础 的文章。

<center><img src="https://cloud-image.ullrai.com/q/Floyd_Warshall_algorithm_diagram/" alt="Floyd_Warshall_algorithm_diagram"/></center>