图算法之Floyd-Warshall 算法（全点对最短路径）详细解读

Floyd-Warshall 算法是用于解决全点对最短路径问题的一种经典算法。该算法的目标是计算一个图中每一对顶点之间的最短路径，适用于加权图，并且可以处理有向图和无向图。与 Dijkstra 算法不同，Floyd-Warshall 算法可以处理负权边，但不允许图中存在负权环。

Floyd-Warshall 算法基本思想

Floyd-Warshall 算法通过动态规划的方式逐步改进顶点间的路径估计值，最终找到从任意一个顶点到另一个顶点的最短路径。其核心思想是，依次将每个顶点作为中间点，更新通过这个中间点的可能更短的路径。

关键思想

对于每一对顶点 i 和 j，如果顶点 k 是一个中间顶点，那么路径 i -> j 的最短距离 dist[i][j] 可以通过比较以下两者来更新：

直接从 i 到 j 的距离 dist[i][j]。
通过顶点 k 作为中间点的路径，即 dist[i][k] + dist[k][j]。

通过不断增加新的中间点，Floyd-Warshall 算法能够在三重循环的过程中更新每一对顶点之间的最短路径。

算法步骤

初始化：
- 使用邻接矩阵表示图，其中 dist[i][j] 表示从顶点 i 到顶点 j 的初始距离。如果 i 和 j 之间没有边，则 dist[i][j] 设为 ∞（代表不可达）；如果 i == j，则 dist[i][j] = 0（到自身的距离为 0）。
动态规划过程：
- 对于每个中间顶点 k，尝试通过顶点 k 来更新每对顶点 i 和 j 之间的距离。如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j]。
重复更新：
- 遍历所有可能的中间顶点，最终得到每对顶点之间的最短路径。

伪代码

下面是 Floyd-Warshall 算法的伪代码：

for k from 1 to n: // k 是中间顶点for i from 1 to n: // i 是起点for j from 1 to n: // j 是终点if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]

时间复杂度

时间复杂度：Floyd-Warshall 算法的时间复杂度为 O(n3)O(n^3)O(n3)，其中 nnn 是图中顶点的数量。由于该算法需要三重嵌套循环，效率相对较低，但适合处理密集图或当边数接近顶点数平方的情况下使用。
空间复杂度：需要 O(n2)O(n^2)O(n2) 的空间来存储所有顶点之间的距离。

适用场景

Floyd-Warshall 算法适用于以下场景：

当图中包含负权边时（但不能有负权环）。
需要计算所有顶点对之间的最短路径时。
图是密集图（顶点之间的边比较多）。

Java 实现

下面是 Floyd-Warshall 算法的 Java 实现：

import java.util.Arrays;public class FloydWarshallAlgorithm {// 定义一个常量表示无穷大（不可达）private static final int INF = 99999;// Floyd-Warshall 算法实现public static void floydWarshall(int[][] graph) {int numVertices = graph.length; // 顶点数量int[][] dist = new int[numVertices][numVertices];// 初始化距离数组for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {dist[i][j] = graph[i][j];}}// 三重循环更新每一对顶点的最短路径for (int k = 0; k < numVertices; k++) {for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {// 通过 k 更新 i 到 j 的最短路径if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}// 打印最终的最短路径矩阵printSolution(dist);}// 打印最终的最短路径矩阵private static void printSolution(int[][] dist) {System.out.println("从各个顶点到其他顶点的最短距离矩阵：");for (int i = 0; i < dist.length; i++) {for (int j = 0; j < dist.length; j++) {if (dist[i][j] == INF) {System.out.print("INF ");} else {System.out.print(dist[i][j] + "   ");}}System.out.println();}}public static void main(String[] args) {// 示例图的邻接矩阵表示int[][] graph = {{0, 3, INF, INF},{2, 0, INF, 5},{INF, 1, 0, 2},{INF, INF, 3, 0}};// 执行 Floyd-Warshall 算法floydWarshall(graph);}
}

代码解读

输入：
- 使用一个二维数组 graph 表示图，其中 graph[i][j] 表示从顶点 i 到顶点 j 的边权值。如果顶点之间没有边，设为 INF 表示不可达。
floydWarshall 方法：
- 初始化距离矩阵 dist 为邻接矩阵。
- 三重循环遍历每个中间顶点 k，然后尝试更新 i -> j 之间的最短路径。
路径更新：
- 通过中间顶点 k，尝试更新 dist[i][j]。如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新为较小的值。
结果输出：
- 使用 printSolution 方法输出最终的最短路径矩阵，若某对顶点之间不可达，则输出 INF。

测试数据

示例图的邻接矩阵为：

    0      3    INF    INF2      0    INF    5INF      1      0      2INF    INF      3      0

该矩阵表示：

节点 0 到节点 1 的边权为 3，节点 1 到节点 0 的边权为 2。
节点 1 到节点 3 的边权为 5，节点 2 到节点 3 的边权为 2，等等。

算法会最终计算出所有顶点对之间的最短路径。

输出结果

执行完 Floyd-Warshall 算法后，最终的最短路径矩阵如下：

0   3   4   6
2   0   3   5
3   1   0   2
5   3   3   0

负权边和负权环

负权边：Floyd-Warshall 算法可以处理负权边，因为它在每一步中比较不同路径的权重并选择最小值。然而，它不能处理负权环（从某个顶点出发，经过一系列顶点又回到该顶点，且路径总权重为负）。
负权环检测：在 Floyd-Warshall 算法执行结束后，若存在 dist[i][i] < 0 的情况，则说明图中存在负权环。