🧮 Floyd-Warshall算法 (Floyd-Warshall Algorithm)

难度 / Difficulty: 困难 (Hard)
分类 / Category: 最短路径 / 动态规划 (Shortest Path / Dynamic Programming)
时间复杂度 / Time Complexity: O(V³)
空间复杂度 / Space Complexity: O(V²)

📖 算法简介 / Introduction

Floyd-Warshall 算法是经典的动态规划算法，用于计算所有节点对之间的最短路径，适用于有向加权图（可含负权边，但不能有负环）。

Floyd-Warshall is a classic dynamic programming algorithm that computes shortest paths between all pairs of vertices in a directed weighted graph. It handles negative edge weights but not negative cycles.

💡 算法原理 / Principle

核心思想：对每一对节点 (i, j)，尝试经过每个中间节点 k 是否能缩短路径。

核心公式：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

逐步增加允许的中间节点集合，从只允许节点1，到允许节点1、2……直到允许全部节点。

三维视角：令 dp[k][i][j] 表示仅使用前 k 个节点（1 到 k）作为中转时，i 到 j 的最短路径。

转移方程：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

滚动数组优化后只需二维数组，遍历 k 时逐步更新。

Core idea: For each pair (i, j), try whether going through intermediate node k produces a shorter path.

The algorithm iteratively refines the shortest path estimate by considering each vertex as a possible intermediate point. Initially, only direct edges are considered; then one by one, we allow paths to use additional vertices as intermediate nodes.

📝 代码实现 / Implementation

Python 实现（详细注释版）

def floyd_warshall(n, edges):
    """
    Floyd-Warshall 算法求所有节点对最短路径

    参数:
        n: 节点数量（节点编号 0 到 n-1）
        edges: 边列表，每条边为 (u, v, w)，表示 u -> v 权重为 w

    返回:
        dist: n x n 距离矩阵，dist[i][j] 表示 i 到 j 的最短距离
    """
    INF = float('inf')
    # 初始化距离矩阵
    dist = [[INF] * n for _ in range(n)]

    # 自身到自身距离为 0
    for i in range(n):
        dist[i][i] = 0

    # 读取所有直接边
    for u, v, w in edges:
        dist[u][v] = w  # 有向图，只更新一个方向

    # 核心：动态规划更新
    # k 是中间节点，尝试通过 k 中转是否能缩短 i 到 j 的路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist


# ============ 示例测试 ============
if __name__ == "__main__":
    # 构造一个简单的有向加权图
    # 节点: 0, 1, 2, 3
    #
    #       2 ← 0 → 3
    #       ↑   ↓   ↑
    #       1 ← — +

    n = 4
    edges = [
        (0, 1, 5),   # 0 -> 1，权重 5
        (0, 2, 3),   # 0 -> 2，权重 3
        (1, 2, -2),  # 1 -> 2，权重 -2（负权边）
        (1, 3, 6),   # 1 -> 3，权重 6
        (2, 3, 2),   # 2 -> 3，权重 2
    ]

    dist = floyd_warshall(n, edges)

    print("所有节点对最短距离矩阵:")
    print("    0    1    2    3")
    for i in range(n):
        row = [f"{dist[i][j]:4}" for j in range(n)]
        print(f"{i}: {' '.join(row)}")

    print(f"\n0 → 3 的最短距离: {dist[0][3]}")  # 期望: 5 (0→2→1→3 路径)

运行结果：

所有节点对最短距离矩阵:
    0    1    2    3
0:   0    5    3    5
1: inf   0   -2    0
2: inf inf   0    2
3: inf inf inf   0

0 → 3 的最短距离: 5

Java 实现（面试白板版）

public class FloydWarshall {
    public static int[][] floydWarshall(int n, int[][] edges) {
        final int INF = Integer.MAX_VALUE;
        int[][] dist = new int[n][n];

        // 初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
            }
        }

        // 读边
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            dist[u][v] = w;
        }

        // 核心动态规划
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;  // 剪枝优化
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue;  // 剪枝优化
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {
            {0, 1, 5}, {0, 2, 3},
            {1, 2, -2}, {1, 3, 6},
            {2, 3, 2}
        };

        int[][] dist = floydWarshall(n, edges);
        System.out.println("0 → 3 = " + dist[0][3]);  // 输出: 5
    }
}

✨ 示例解析 / Example Analysis

问题： 4节点有向图，边如下：

0 → 1 (权重 5)    1 → 3 (权重 6)
0 → 2 (权重 3)    2 → 3 (权重 2)
1 → 2 (权重 -2)

手动推导 0 → 3 的最短路径：

最终答案是 5。最短路径可能是 0→2→3 或 0→1→2→3。

🔍 算法对比 / Comparison

当需要多源最短路径时，Dijkstra 需要运行 V 次，总复杂度 O(V³ log V)，与 Floyd-Warshall 相同，但 Floyd-Warshall 实现更简洁，且天然支持负权边。

🎯 适用场景 / Scenarios

• 路由算法：计算网络中所有节点对的最短路径（如 OSPF 内部网关协议）
• 传递闭包：检测图中任意两点是否可达（Floyd-Warshall 的布尔版本）
• 负环检测：用于检测金融网络中是否存在套利机会（Bellman-Ford的变体）
• 近似算法：作为下界，用于旅行商问题（TSP）的启发式求解
• 多源多汇网络流：需要知道任意两点间的距离来优化流分配

⚠️ 注意事项 / Caveats

1. 不能处理负环：如果图中存在负环，最短路径无定义（Floyd-Warshall 会不断更新导致错误结果）。可额外检测对角线上的负值来检测负环。

2. 稠密图效率高：当图稠密时（F² ≈ V²），Floyd-Warshall 的三循环结构实际运行很快；而稀疏图用 Dijkstra + 堆更优。

3. 路径重构：实际应用中往往需要记录前驱节点 next[i][j] 或 next[i][j]，在更新时同步记录，复杂度仅加 O(1)。

🔄 扩展阅读 / Further Reading

• 负环检测：在算法结束后检查 dist[i][i] < 0 的节点，即可发现负环
• 路径重构：使用 next[i][j] 记录从 i 到 j 的下一步，完整路径可递归回溯
• 优化方向：对于极大图，可采用「分治 Floyd-Warshall」或「基于排序的算法」
• 对比学习：建议同时学习 Dijkstra（单源）、Bellman-Ford（单源+负权）、SPFA（队列优化版 Bellman-Ford）

📚 参考资料 / References

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), Chapter 25
• 维基百科: Floyd-Warshall algorithm