Floyd-Warshall 算法：最短路径查找

1. 概述

Floyd-Warshall 算法是一种用于查找带权有向图中所有顶点对之间最短路径的经典动态规划算法。本文将介绍该算法的基本思想、实现逻辑，并对其时间复杂度进行分析。

2. Floyd-Warshall 算法详解

该算法适用于带权有向图，通过动态规划逐步优化每对顶点之间的最短路径估计值。其核心思想是：如果从顶点 i 到顶点 j 的路径经过某个中间顶点 k 后更短，则更新最短路径值。

算法步骤

初始化距离矩阵 distance[i][j]：
- 主对角线（即 i == j）设为 0。
- 其他位置根据图中边的权重初始化，无边则设为无穷大（∞）。
使用三重循环，依次以每个顶点 k 作为中间节点，尝试更新所有顶点对 (i, j) 的最短路径。
若 distance[i][j] > distance[i][k] + distance[k][j]，则更新 distance[i][j]。

示例伪代码

algorithm FloydWarshall(G):
    // 初始化距离矩阵
    for d in V:
        distance[d][d] <- 0
    for edge (s, p) in E:
        distance[s][p] <- weight(s, p)

    // 三重循环更新最短路径
    n <- cardinality(V)
    for k <- 1 to n:
        for i <- 1 to n:
            for j <- 1 to n:
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] <- distance[i][k] + distance[k][j]

3. 示例演示

我们来看一个具体的带权有向图：

1-1

构造初始距离矩阵如下：

$$ \begin{bmatrix} 0 & \infty & -2 & \infty \ 4 & 0 & 3 & \infty \ \infty & \infty & 0 & 2 \ \infty & -1 & \infty & 0 \ \end{bmatrix} $$

通过迭代更新，最终得到所有顶点对之间的最短路径矩阵：

$$ \begin{bmatrix} 0 & -1 & -2 & 0 \ 4 & 0 & 2 & 4 \ 5 & 1 & 0 & 2 \ 3 & -1 & 1 & 0 \ \end{bmatrix} $$

✅ 注意： 由于存在负权边，Floyd-Warshall 仍能正确运行，但不能处理存在负权环的情况。

4. 时间复杂度分析

算法核心是三重嵌套循环，每层循环最多运行 n 次（n 为顶点数量），因此总时间复杂度为：

$$ \mathcal{O}(n^3) $$

✅ 优点：

简洁易实现
可处理负权边（但不能有负权环）

❌ 缺点：

时间复杂度高，不适用于大规模图（顶点数超过几百时效率明显下降）

5. 总结

Floyd-Warshall 是一种适用于稠密图和所有顶点对最短路径问题的经典算法。尽管其时间复杂度为 O(n³)，但在中等规模图中表现良好，适合教学和小规模图结构分析。

📌 适用场景：

图中顶点数量有限
需要获取所有顶点对之间的最短路径
图中可能存在负权边（但不能有负权环）

📌 不适用场景：

图中顶点数较大（如几千以上）
图中存在负权环（会导致算法失效）

Persistence

REST

Security