Floyd-Warshall算法

Floyd-Warshall 算法（也称为 Floyd-Warshall 算法或三重算法），以 Robert Floyd 和 Stephen Warshall 的名字命名，是一种图论算法。 在 Floyd 的版本中，他找到图中所有节点对之间的最短路径并计算它们的长度（APSP，所有对最短路径）。 在 Warshall 的版本中，他发现了图的传递闭包。 这两个版本都是在 1962 年提出的，可以追溯到 Stephen Kleene 在 1956 年发表的与正则表达式相关的算法。

Floyd-Warshall 算法的运行时间（复杂度）为 O ( n 3 ) ，因为对于三个变量 k ， i , j 从1到n 的值都要跑一遍。 其中 n 是图中的节点数。

Floyd-Warshall 算法是计算密集图中所有节点对之间路径的不错选择，其中大多数或所有节点对由边连接。 对于非负边权的稀疏图，xxx从每个可能的起始节点开始使用Dijkstra算法，因为重复Dijkstra的运行时间为O ( | E | | V | + | V | 2 log ⁡ | V | )使用斐波那契堆比运行时间 O ( | V | 3 )， 如果 | 乙 | 明显小于 | 五| 2 是对于具有负边但没有负环的稀疏图，可以使用与 Dijkstra 重复方法相同的渐近运行时间的 Johnson 算法。

还已知使用快速矩阵乘法来加速计算密集图中所有顶点对之间的最短路径的算法，但这些算法通常会对边权重做出额外的假设，例如他们需要小整数。 由于运行时间中的高常数因子，与非常大的图的 Floyd-Warshall 算法相比，它们只会导致加速。

以下 C# 编程语言示例显示了 Floyd-Warshall 算法的实现。 的有向图。 程序执行使用 Main 方法，它将所有节点对之间的最短距离返回到控制台。 距离矩阵存储在数据类型为整数的二维数组中。 如果节点未连接，则输出值无穷大。

在外循环的xxx次迭代之前，由上面的 k = 0 表示，xxx已知的路径对应于图中的每条边。 在 k = 1 时，找到通过节点 1 的路径：特别是，找到替代边数较少但较长的路径的路径。 对于 k=0、d=3 和 k=1，该值被 d=d+d=4+(-2)=2 覆盖。 对于 k = 2，找到通过节点 {1,2} 的路径。 红色和蓝色框显示了路径是如何从两条已知路径组装而成的，并且在之前的迭代中遇到过交叉点 2。 路径不考虑，因为是从2到3到目前为止遇到的最短路径。 当 k = 3 时，找到所有通过节点 {1,2,3} 的路径。 最后，在 k = 4 时，找到所有最短路径。

• Min-Plus 矩阵乘法算法
• A*算法
• Dijkstra 算法
• 贝尔曼-福特算法