数据结构与算法 / 系统课时
Floyd 怎么求全源最短路
Floyd 怎么求全源最短路
Floyd-Warshall 适合一次求出任意两点之间的最短距离。它的关键不是记住三重循环,而是理解“允许哪些中间点参与路径”的状态含义;只要把 k 放在最外层,原地更新距离矩阵就能得到全源最短路。
学习目标
- 解释 Floyd-Warshall 的状态定义与三重循环顺序
- 写出可运行的全源最短路实现,并验证距离矩阵
- 判断它对负权边、负环、图规模和空间开销的适用边界
状态为什么能逐步放宽
先令 dist[i][j] 表示当前已知的 i 到 j 最短距离。初始时,只允许使用直接边:对角线为 0,有边就记录边权,没有边则为无穷大;若同一方向存在多条边,应保留最小边权。
处理顶点 k 时,任意一条从 i 到 j 的最短路只有两种可能:不经过 k,或经过 k。因此状态转移就是在原距离与“先到 k、再从 k 到终点”的距离之间取较小值。

k 必须放在最外层,因为第 k 轮结束后,需要保证矩阵中的路径只使用已经开放的中间点。把 i 或 j 放到最外层,会破坏这个逐层扩展的状态语义,不能再按同一转移证明正确性。
用三重循环完成实现
下面用一个 4 个顶点的有向图验证算法。实现先构造距离矩阵,再按 k → i → j 的顺序尝试松弛;当两段路径中任意一段不可达时直接跳过,既清晰也避免无意义的加法。
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))预期输出
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
时间复杂度为 ,空间复杂度为 。因此它常用于顶点数较小、需要大量点对查询,或图较稠密而矩阵表示本就合理的场景。若顶点达到几万,即使边不多,距离矩阵的空间也通常已经不可接受。
只有单源查询且边权非负时,Dijkstra 往往更合适;无权图应优先 BFS。Floyd 的优势是实现稳定、一次得到所有点对答案,并且负权边也能处理,但代价是固定的三次方时间和平方级内存。