Floyd-Warshall 算法

Published: Sun Feb 15 2026 | Modified: Wed Feb 18 2026 , 3 minutes reading.

Floyd-Warshall：图论中的上帝视角

算法背后的故事：“中间人”的力量

1962 年，计算机科学界正在热议一个问题：“传递闭包 (Transitive Closure)”。这个听起来很学术的名词，其实描述了一个简单的社交概念：如果 Alice 认识 Bob，而 Bob 认识 Charlie，那么 Alice 实际上也就认识了 Charlie。

Robert Floyd 和 Stephen Warshall 几乎在同一时间独立发表了解决这个问题的算法。他们意识到，要理解一张图，并不需要亲自在里面奔波。你只需要系统性地引入“中间人”。

他们的算法与众不同。它没有起点，也没有终点。它只是静静地注视着整个数据宇宙，然后问一个问题：“如果我让每个人都充当一次联络员，我们能不能看清所有人之间的真正关系？”

为什么需要它？

Dijkstra 和 A* 是 单源 (Single-Source) 算法。它们告诉你如何从家到 任何地方。但有时候，你需要的是 全源 (All-Pairs) 的知识。

网约车调度： 系统需要瞬间知道 每一辆车 到 每一个乘客 的距离。
社交网络分析： 要确定谁是社交圈的“中心”，你需要知道他离 其他人 到底有多近。

运行 N 次 Dijkstra 既麻烦又难写。Floyd-Warshall 用一种极度优雅的方式，一次性交给你一张包含所有距离的终极表格。

算法是如何“思考”的

Floyd-Warshall 可能是图论中最优雅——也可能是最傲慢——的算法。它以一种 “上帝模式 (God-Mode)” 进行思考。

布局： 它首先铺开一张巨大的表格（矩阵），代表当下的世界。
- 如果 $i$ 和 $j$ 之间有直接的路，写下成本。
- 如果没有，写下 $\infty$ 。
- 任何人到自己的距离都是 0。
引荐： 然后，它开始了一场循环。它选中一个节点——我们叫它 $k$ ——并将它作为 “中间人” 介绍给全世界。它会问每一对节点 ( $i$ 和 $j$ ) 一个问题：
“嘿 $i$ ，你现在是直接去 $j$ （或者根本到不了）。但如果你经由 $k$ 中转一下 ( $i \to k \to j$ )，会不会更快？”
如果答案是肯定的，世界地图就会瞬间更新。旧的路被遗忘，经由中间人的新路成为了标准。
共识： 它会对图中的每一个节点重复这个过程。首先是节点 A 当中间人，然后是 B，然后是 C…… 当最后一个节点也完成中间人的使命时，矩阵中留下的，就是任意两点间确凿无疑的最短路径。

“松弛”的逻辑

这种“检查第三方能否改善关系”的逻辑，正是 动态规划 (Dynamic Programming) 的核心。它自底向上地构建解决方案，确保在结束时，没有任何更短的路径被遗漏，因为每一种组合都被测试过了。

工程决策：全知全能的代价

Floyd-Warshall 的代码短得惊人——核心逻辑只有四行。但这种优雅伴随着沉重的代价： $O(V^3)$ 的复杂度。

对于 100 个节点，它做约 100 万次运算。（瞬间完成）
对于 1,000 个节点，它做约 10 亿次运算。（很慢）
对于 10,000 个节点，它做约 1 万亿次运算。（算不完）

什么时候用它？

小型稠密图： 当节点少于 500 个，但连接非常密集时（比如管理主要机场之间的航线）。
预计算 (Pre-computation)： 当地图很少变化时，你愿意支付一次昂贵的计算成本，以换取未来每一次查询都是 $O(1)$ 的极致速度。

实现参考 (Python)

这可能是你写过的最短的路径算法代码。

def floyd_warshall(graph_matrix):
    """
    graph_matrix: 二维列表 (V x V)，graph_matrix[i][j] 是权重。
    不相连则用 float('inf') 表示。
    """
    V = len(graph_matrix)
    
    # 我们创建一个副本，避免直接修改输入数据
    dist = [row[:] for row in graph_matrix]

    # 核心：三个嵌套循环
    # k = 中间人
    # i = 起点
    # j = 终点
    for k in range(V):
        for i in range(V):
            for j in range(V):
                
                # 黄金问题：
                # 经由 k 中转，是否比当前已知的路 (i->j) 更快？
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 使用示例
# inf = float('inf')
# graph = [
#     [0,   5,   inf, 10],
#     [inf, 0,   3,   inf],
#     [inf, inf, 0,   1],
#     [inf, inf, inf, 0]
# ]
# print(floyd_warshall(graph))

小结

Floyd-Warshall 教会了我们视角的价值。它不急于从 A 奔向 B，而是通过系统性地建立共识，一遍又一遍地询问：“如果我们要经过中间人协作，能不能做得更好？” 它很慢，但它极其彻底——最终，它知晓一切。

Luke Sun