Floyd-Warshall 算法

定义

Floyd-Warshall 算法用于求解带权图中所有顶点对之间的最短路径,由 Robert Floyd 与 Stephen Warshall 等人分别独立提出,是动态规划思想的典型应用。

原理

设 d[i][j] 表示 i 到 j 的最短距离,算法以每个顶点 k 作为中转点,依次尝试用 d[i][k]+d[k][j] 更新 d[i][j]。三重循环结束后即得到全源最短路径矩阵。允许负权边,但不允许负权环;通过检查对角线元素是否为负可以发现负环。

应用

适合顶点数较小(几百以内)且需要任意两点间距离的场景,如网络时延矩阵计算、传递闭包求解、图的中心度分析等。

优缺点

实现极其简洁,仅需十行左右代码;缺点是 O(V³) 的时间与 O(V²) 的空间开销使其无法用于大规模图。