数据结构与算法 / 系统课时

Floyd 怎么求全源最短路

Floyd 怎么求全源最短路

Floyd-Warshall 适合一次求出任意两点之间的最短距离。它的关键不是记住三重循环,而是理解“允许哪些中间点参与路径”的状态含义;只要把 k 放在最外层,原地更新距离矩阵就能得到全源最短路。

学习目标

  • 解释 Floyd-Warshall 的状态定义与三重循环顺序
  • 写出可运行的全源最短路实现,并验证距离矩阵
  • 判断它对负权边、负环、图规模和空间开销的适用边界

状态为什么能逐步放宽

先令 dist[i][j] 表示当前已知的 i 到 j 最短距离。初始时,只允许使用直接边:对角线为 0,有边就记录边权,没有边则为无穷大;若同一方向存在多条边,应保留最小边权。

处理顶点 k 时,任意一条从 i 到 j 的最短路只有两种可能:不经过 k,或经过 k。因此状态转移就是在原距离与“先到 k、再从 k 到终点”的距离之间取较小值。

Dk(i,j)=min⁡(Dk−1(i,j),Dk−1(i,k)+Dk−1(k,j))D_k(i,j)=\min\left(D_{k-1}(i,j),D_{k-1}(i,k)+D_{k-1}(k,j)\right)

Floyd 逐步放宽中间点集合的状态转移

k 必须放在最外层,因为第 k 轮结束后,需要保证矩阵中的路径只使用已经开放的中间点。把 i 或 j 放到最外层,会破坏这个逐层扩展的状态语义,不能再按同一转移证明正确性。

用三重循环完成实现

下面用一个 4 个顶点的有向图验证算法。实现先构造距离矩阵,再按 k → i → j 的顺序尝试松弛;当两段路径中任意一段不可达时直接跳过,既清晰也避免无意义的加法。

python
from math import inf

def floyd_warshall(n, edges):
    dist = [[inf] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    # 多重边只保留同方向的最小权值。
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)

    for k in range(n):
        for i in range(n):
            if dist[i][k] == inf:
                continue
            for j in range(n):
                if dist[k][j] == inf:
                    continue
                candidate = dist[i][k] + dist[k][j]
                if candidate < dist[i][j]:
                    dist[i][j] = candidate

    return dist

def print_matrix(dist):
    for row in dist:
        print(' '.join('INF' if x == inf else str(x) for x in row))

if __name__ == '__main__':
    edges = [
        (0, 1, 3),
        (0, 2, 10),
        (1, 2, 1),
        (1, 3, 7),
        (2, 3, 2),
    ]
    print_matrix(floyd_warshall(4, edges))

预期输出

text
0 3 4 6
INF 0 1 3
INF INF 0 2
INF INF INF 0

输出中 0 → 3 的最短距离从直接不可达变成 6,对应路径 0 → 1 → 2 → 3。如果原图是无向图,需要把每条边 (u, v, w) 同时加入 (v, u, w),再执行同样的算法。

负权边和负环怎么处理

Floyd-Warshall 可以处理负权边,因为它不依赖“当前最小距离已经确定”这一前提。但如果图中存在可达负环,就可以反复绕环让路径长度持续下降,此时相关点对不存在有限的最短距离。

完整计算后,只要发现某个 dist[v][v] < 0,就说明顶点 v 位于负环上或可经闭路回到自身且总权为负。若题目要求进一步判断哪些点对受负环影响,还需要继续结合可达关系传播,而不能只返回普通距离值。

什么时候适合用 Floyd

时间复杂度为 O(V3)O(V^3),空间复杂度为 O(V2)O(V^2)。因此它常用于顶点数较小、需要大量点对查询,或图较稠密而矩阵表示本就合理的场景。若顶点达到几万,即使边不多,距离矩阵的空间也通常已经不可接受。

只有单源查询且边权非负时,Dijkstra 往往更合适;无权图应优先 BFS。Floyd 的优势是实现稳定、一次得到所有点对答案,并且负权边也能处理,但代价是固定的三次方时间和平方级内存。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Floyd 怎么求全源最短路

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通