Floyd-Warshall：全源最短路的方阵演算

Floyd-Warshall：全源最短路的方阵演算

从 Warshall 研究传递闭包时的一个观察说起：布尔矩阵自乘能算出"谁能到达谁"，而把布尔与或换成加和取小，同样的三重循环就能算出"谁到谁最省"。这就是 Floyd-Warshall 算法的来路——最短路战役收官之战的部队。前两节都在解单源问题（一个起点到所有点），本节把镜头拉到全景：任意两据点之间的最短路，一次性全部算清。它直接作业在第 2 章的邻接矩阵上，稠密地形上的全源问题几乎总是它的主场。本节也是全册第一次正式动用动态规划的思想骨架，为后续章节的思维升级埋下伏笔。

战役背景：全源问题长什么样

全源最短路要求输出一整张距离表：行是起点、列是终点、格子里是最短距离。它的需求方随处可见——地图服务预计算城市间里程矩阵、交通规划评估全网可达性、社交平台批量计算用户距离、图数据库回答任意两点的关系最短链。

解法上有两条路。其一是"复用单源"：对每个顶点各跑一次 Dijkstra，堆优化下总代价是"顶点数乘边数再乘一个对数因子"——稀疏图上非常划算。其二是本节的主角：三重循环直接在矩阵上推演，代价固定为顶点数的立方量级，与边数无关。边数越稠密，立方量级的相对优势越明显；顶点数不大时（数千以内），它简单、稳定、常数小，几乎是默认选择。

思路推演：允许谁当中转

算法的灵魂是给最短路的定义加一个逐步放宽的限制：只允许经过编号不超过 k 的中转顶点。把这个限制记进状态——d(k, i, j) 表示从 i 到 j、仅允许前 k 号顶点做中转的最短距离——递推关系便自然浮现：

d(k, i, j) = min( d(k-1, i, j), d(k-1, i, k) + d(k-1, k, j) )

读成一句人话：放宽到允许 k 号中转后，i 到 j 的最短路要么根本不经过 k（沿用旧值），要么恰好经过 k 一次（两段旧值相接）。为什么"恰好一次"就够了？若经过 k 多次，路上就有以 k 为交点的环，零环去掉不亏、正环去掉更短——最短路总能取到"至多经过 k 一次"的形态。递推的起点 d(0, i, j) 就是原始邻接矩阵（无边处记无穷），而 k 放宽到顶点总数时，一切中转皆被允许，d 的极限正是真·全源距离表。

算法步骤与实现

代码短得出名——初始化矩阵，三层循环，完事。但短代码里埋着最经典的次序陷阱，实现后再展开：

import networkx as nx

def floyd_warshall(G):
    """返回 全源距离矩阵（字典套字典）"""
    INF = float("inf")
    dist = {u: {v: (0 if u == v else INF) for v in G.nodes} for u in G.nodes}
    for u, v, d in G.edges(data=True):
        w = d["weight"]
        if w < dist[u][v]:                     # 平行边取更短
            dist[u][v] = w
            dist[v][u] = w                     # 无向图对称登记
    nodes = list(G.nodes)
    for k in nodes:                            # 中转点：必须最外层
        dk = dist[k]
        for i in nodes:
            dik = dist[i][k]
            if dik == INF:                     # i 到 k 不通，跳过整行
                continue
            di = dist[i]
            for j in nodes:
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd                 # 借道 k 更近则刷新
    return dist

grid = nx.Graph()
grid.add_weighted_edges_from([("北门","校场",3),("校场","南仓",5),
                              ("北门","东桥",7),("东桥","南仓",1),
                              ("校场","东桥",2)])
dist = floyd_warshall(grid)
for u in ["北门", "校场"]:
    print(u, "→", {v: dist[u][v] for v in grid.nodes})
# networkx 官方对照
ref = nx.floyd_warshall(grid)
print("nx 对照 北门→南仓:", ref["北门"]["南仓"], "手算:", dist["北门"]["南仓"])
​

几处工程细节：预取 dist[i][k] 与 dist[k] 到局部变量，让最内层只做一次加法一次比较——Python 这类解释型语言里，这类"减少字典查找"的手法能换来数倍加速；dik == INF 的跳过避免无穷运算的噪声；对角线初始化为零而不是依赖自环，保证"到自己零距离"这条公理无条件成立。

次序为什么不能换：若把 k 放进最内层，某次刷新用的可能是"本轮已经放宽过 k 的值"，状态定义被打乱——不是错在答案偶尔也对，而是正确性论证失效，构造出反例输入并不难。动态规划的代码往往以"循环次序即状态推进次序"的面目出现，这一条是本节最该带走的工程直觉。

复杂度与正确性

代价账单干净：三层循环各与顶点数同阶，总体立方量级，且与边数无关——图再稠密也是这个价。空间上，滚动掉 k 维后只需一张距离矩阵，若要还原路径再加一张"后继表"记录每格当前的中转决策，回溯时顺藤摸瓜即可展开完整路线。正确性由归纳背书：对 k 归纳，每一步放宽引入新中转点 k 时，递推式恰好枚举了"不经 k"与"恰经 k 一次"两种可能，而无环性论证保证后者两段都是旧限制下的精确值——命题层层成立，终止时限制放宽到全体顶点，得到的就是无约束的真最短路。负权边不碍事（它没有"定稿封箱"的操作），但负环依旧致命：跑完后对角线上若出现负数，就是负环的自白——全源版负环检测，白送。

应用与变体

这个三重循环的骨架比它看上去通用得多。把"取小、相加"换成"取与、取或"，它计算传递闭包——第 4 章可达性判定的矩阵解法；把运算换成"取大、相加"，它进入半环代数的天地，能算网络的可靠性、任务的最早完成时刻，乃至语音识别里的维特比解码同源思想。工程实践里，城市间里程预计算、图数据库的多对多距离查询、网格地图游戏的战棋寻路，都是它的直接阵地；而"边权动态变化后如何增量更新距离表"则是它活跃的研究前沿——重跑整个立方循环太奢侈，学者们为局部扰动设计了许多聪明的修补术。

⚠️ 常见坑：顶点数上千还坚持用 Floyd。立方量级的增长极其凶悍，顶点数翻倍代价翻八倍；稀疏大图请回到"逐点 Dijkstra"的路线，别让方阵的美感绑架选型。

💡 关键直觉：Floyd 的世界观是"限制逐步放宽"——先画地为牢（只准走前 k 号），再一轮轮拆墙。动态规划的很多杰作都是这个套路：把"无约束的难题"拆成"约束强度递增的一串易题"。

最短路战役至此全胜。远征队接下来转入另一场与"最省"有关的战役——不是走得最短，而是用最省的代价把所有据点连成一张网：最小生成树与行军调度。