OI-wiki 最短路算法完全指南Floyd、Bellman–Ford、Dijkstra 与 Johnson 全解析【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本篇技术指南以 OI-wiki 中 docs/graph/shortest-path.md 为骨架系统讲解图论中最短路问题的四大经典算法全源最短路 Floyd、可处理负权与负环检测的 Bellman–Ford及其队列优化 SPFA、非负权图上效率最高的单源最短路 Dijkstra以及把 Dijkstra 推广到任意图的全源算法 Johnson。读完本文你将掌握每种算法的适用场景、复杂度边界、正确性论证与可直接落地的 C/Python 实现并能在 OI / ICPC 竞赛中根据边权符号、图密度与最短路类型做出正确选型。前置定义与记号在阅读算法之前先明确最短路问题的基本概念完整基础可参考 图论相关概念路径图上由边依次连接的点列。最短路两点之间所有路径中边权和最小者。有向图 / 无向图最短路两者在算法上通用但需要注意方向性细节例如无向图求最小环与有向图求最小环的公式不同。单源最短路固定源点 $s$求 $s$ 到其余所有点的最短路。每对结点之间的最短路求图中任意两点之间的最短路全源最短路。为了统一叙述定义如下记号记号含义$n$图上点的数目$m$图上边的数目$s$最短路的源点$D(u)$$s$ 点到 $u$ 点的实际最短路长度$dis(u)$$s$ 点到 $u$ 点的估计最短路长度任何时候都有 $dis(u) \geq D(u)$算法终止时应满足 $dis(u)D(u)$$w(u,v)$边 $(u,v)$ 的边权最短路的基本性质对于边权为正的图最短路具有以下三条重要性质任意两个结点之间的最短路不会经过重复的结点任意两个结点之间的最短路不会经过重复的边任意一条最短路的结点数不会超过 $n$边数不会超过 $n-1$。第 3 条性质是所有「逐轮松弛、至多 $n-1$ 轮收敛」类算法如 Bellman–Ford的复杂度论证基础。Floyd 算法全源最短路Floyd 算法用于求任意两个结点之间的最短路。它的复杂度较高$O(N^3)$但常数小、实现极简核心只有三个for且适用于任何图——无论有向无向、边权正负只要最短路存在即可图中不能存在负环。状态设计与转移定义数组f[k][x][y]表示只允许经过结点 $1$ 到 $k$时即在子图 $V{1,2,\dots,k}$ 中取中间点注意 $x$ 与 $y$ 本身不一定在该子图中结点 $x$ 到结点 $y$ 的最短路长度。显然f[n][x][y]就是所求的 $x$ 到 $y$ 的最短路此时中间点集合就是整个点集 $V$。初始值f[0][x][y]$x$ 与 $y$ 有直接相连的边时为其边权$x y$ 时为 $0$自身到自身距离为零否则为 $\infty$。转移方程 $$ f[k][x][y] \min(f[k-1][x][y],; f[k-1][x][k] f[k-1][k][y]) $$ 其中f[k-1][x][y]表示不经过$k$ 点的最短路f[k-1][x][k] f[k-1][k][y]表示经过$k$ 点的最短路。两者取最小值即可。朴素的三维实现如下$k$ 从 $1$ 到 $n$ 依次扩大问题规模 Ccpp for (k 1; k n; k) { for (x 1; x n; x) { for (y 1; y n; y) { f[k][x][y] min(f[k - 1][x][y], f[k - 1][x][k] f[k - 1][k][y]); } } } Pythonpython for k in range(1, n 1): for x in range(1, n 1): for y in range(1, n 1): f[k][x][y] min(f[k - 1][x][y], f[k - 1][x][k] f[k - 1][k][y])第一维的省略与证明因为第一维对结果无影响可以直接省略得到空间优化版 Ccpp for (k 1; k n; k) { for (x 1; x n; x) { for (y 1; y n; y) { f[x][y] min(f[x][y], f[x][k] f[k][y]); } } } Pythonpython for k in range(1, n 1): for x in range(1, n 1): for y in range(1, n 1): f[x][y] min(f[x][y], f[x][k] f[k][y])为什么第一维可以安全省略对于给定的k当更新f[k][x][y]时涉及的元素总是来自f[k-1]数组的第k行和第k列。进一步观察更新f[k][k][y]或f[k][x][k]时数值不会发生改变因为 $$ f[k][k][y] \min(f[k-1][k][y],; f[k-1][k][k]f[k-1][k][y]) $$ 而f[k-1][k][k] 0故该值恒等于f[k-1][k][y]对f[k][x][k]同理。因此在给定的k下每个元素的更新中引用到的元素都没有在本轮迭代中被更新省略第一维不影响结果。最终 Floyd 的时间复杂度为 $O(N^3)$空间复杂度为 $O(N^2)$。应用一求无向图最小权值环给一个正权无向图找一个最小权值和的环。首先最小环一定是一个简单环。考虑环上编号最大的结点 $u$此时f[u-1][x][y]加上边 $(u,x)$ 与 $(u,y)$ 共同构成了这个环。在 Floyd 外层循环枚举到 $ku$ 之前用f[u-1][x][y] w(u,x) w(u,y)更新答案取最小值即可。时间复杂度为 $O(n^3)$。OI-wiki 在 docs/graph/min-cycle.md 中给出了该思路的完整论述Floyd 算法有一个性质——在最外层循环到点 $k$ 时尚未开始第 $k$ 次循环$dis_{u,v}$ 表示的是从 $u$ 到 $v$ 且仅经过编号在 $[1,k)$ 区间中的点的最短路。最小环至少含三个顶点设编号最大的顶点为 $w$环上与 $w$ 相邻的两点为 $u,v$则在枚举到 $kw$ 时环长即为 $dis_{u,v}val(v,w)val(w,u)$。该页同时给出了求最小环的完整 C/Python 参考实现。应用二传递闭包已知一个有向图中任意两点之间是否有连边判断任意两点是否连通。该问题即为求图的传递闭包。只需按照 Floyd 的过程逐个加入点判断此时边权简化为 $1/0$取min运算变成或运算。再用bitset优化复杂度可降至 $O(\frac{n^3}{w})$// std::bitsetSIZE f[SIZE]; for (k 1; k n; k) for (i 1; i n; i) if (f[i][k]) f[i] f[i] | f[k];Bellman–Ford 算法可处理负权并检测负环Bellman–Ford 是一种基于松弛relax操作的最短路算法可以求出带负权图的最短路并能对最短路不存在存在可达负环的情况进行判断。在国内 OI 界常听到的SPFA就是 Bellman–Ford 的一种实现。松弛操作与算法过程对边 $(u,v)$松弛操作对应下面的式子 $$ dis(v) \min(dis(v),; dis(u) w(u,v)) $$ 含义是尝试用「$s \to u$取最短路 边 $(u,v)$」这条路径去更新 $v$ 的最短路长度若更优则更新Dijkstra 同样依赖该操作。Bellman–Ford 的做法是不断尝试对图上每一条边进行松弛每一轮循环对所有边各尝试一次松弛当某轮循环中没有成功发生松弛时算法停止。每次循环代价为 $O(m)$在最短路存在时一次成功的松弛会使最短路的边数至少增加 $1$而最短路边数最多为 $n-1$因此整个算法最多执行 $n-1$ 轮松弛总时间复杂度为 $O(nm)$。负环的判定如果第 $n$ 轮循环时仍然存在能松弛的边说明从 $s$ 点出发可以抵达一个负环——因为对最短路存在的图松弛至多执行 $n-1$ 轮。⚠️负环判断的常见误区以 $s$ 为源点跑 Bellman–Ford 没有报出负环只能说明从 $s$ 出发不能抵达负环并不能说明图上不存在负环。若需判断整个图是否存在负环最严谨的做法是建立超级源点向图上每个结点连一条权值为 $0$ 的边再以超级源点为起点执行 Bellman–Ford。参考实现 C cpp struct Edge { int u, v, w; };vectorEdge edge; int dis[MAXN], u, v, w; constexpr int INF 0x3f3f3f3f; bool bellmanford(int n, int s) { memset(dis, 0x3f, (n 1) * sizeof(int)); dis[s] 0; bool flag false; // 判断一轮循环过程中是否发生松弛操作 for (int i 1; i n; i) { flag false; for (int j 0; j edge.size(); j) { u edge[j].u, v edge[j].v, w edge[j].w; if (dis[u] INF) continue; // 无穷大与常数加减仍然为无穷大 // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作 if (dis[v] dis[u] w) { dis[v] dis[u] w; flag true; } } // 没有可以松弛的边时就停止算法 if (!flag) { break; } } // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环 return flag; } Python python class Edge: definit(self, u0, v0, w0): self.u u self.v v self.w wINF 0x3F3F3F3F edge [] def bellmanford(n, s): dis [INF] * (n 1) dis[s] 0 for i in range(1, n 1): flag False for e in edge: u, v, w e.u, e.v, e.w if dis[u] INF: continue # 无穷大与常数加减仍然为无穷大 # 因此最短路长度为 INF 的点引出的边不可能发生松弛操作 if dis[v] dis[u] w: dis[v] dis[u] w flag True # 没有可以松弛的边时就停止算法 if not flag: break # 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环 return flag 实现中有两个值得注意的细节INF 的选取代码使用0x3f3f3f3f作为无穷大。这是因为0x3f3f3f3f 0x3f3f3f3f不会溢出 32 位有符号整数且可用memset(dis, 0x3f, ...)快速初始化。跳过 INF 结点最短路长度为 INF 的点引出的边不可能发生松弛无穷大与常数加减仍为无穷大跳过可避免无意义的计算。队列优化SPFASPFAShortest Path Faster Algorithm的核心观察是只有上一次被松弛的结点所连接的边才有可能引起下一次松弛操作。因此用队列维护「哪些结点可能引起松弛」就能只访问必要的边。SPFA 同样可以判断 $s$ 点能否抵达负环记录最短路经过的边数cnt当某点最短路边数达到至少 $n$ 时说明经过了负环。 C cpp struct edge { int v, w; };vectoredge e[MAXN]; int dis[MAXN], cnt[MAXN], vis[MAXN]; queueint q; bool spfa(int n, int s) { memset(dis, 0x3f, (n 1) * sizeof(int)); dis[s] 0, vis[s] 1; q.push(s); while (!q.empty()) { int u q.front(); q.pop(), vis[u] 0; for (auto ed : e[u]) { int v ed.v, w ed.w; if (dis[v] dis[u] w) { dis[v] dis[u] w; cnt[v] cnt[u] 1; // 记录最短路经过的边数 if (cnt[v] n) return false; // 在不经过负环的情况下最短路至多经过 n - 1 条边 // 因此如果经过了多于 n 条边一定说明经过了负环 if (!vis[v]) q.push(v), vis[v] 1; } } } return true; } Python python from collections import dequeclass Edge: def __init__(self, v0, w0): self.v v self.w w e [[Edge() for i in range(MAXN)] for j in range(MAXN)] INF 0x3F3F3F3F def spfa(n, s): dis [INF] * (n 1) cnt [0] * (n 1) vis [False] * (n 1) q deque() dis[s] 0 vis[s] True q.append(s) while q: u q.popleft() vis[u] False for ed in e[u]: v, w ed.v, ed.w if dis[v] dis[u] w: dis[v] dis[u] w cnt[v] cnt[u] 1 # 记录最短路经过的边数 if cnt[v] n: return False # 在不经过负环的情况下最短路至多经过 n - 1 条边 # 因此如果经过了多于 n 条边一定说明经过了负环 if not vis[v]: q.append(v) vis[v] True 使用警告虽然 SPFA 在大多数情况下跑得很快但其最坏情况时间复杂度为 $O(nm)$且将其卡到这个复杂度并不难竞赛时需谨慎使用。经验法则是没有负权边时优先使用 Dijkstra有负权边且图无特殊性质时若 SPFA 是标算的一部分题目数据范围应当保证 Bellman–Ford 能通过。仓库中可见 SPFA 的实际工程化应用例如 docs/graph/code/mod-shortest-path/mod-shortest-path_1.cpp同余最短路中注释写明spfa算法可看最短路部分将 SPFA 用于求模意义下的最短路docs/graph/code/diff-constraints/diff-constraints_1.cpp差分约束则以超级源点 0 号结点 SPFA 判负环的方式判断差分约束系统是否有解正是「超级源点判全图负环」思想的直接体现。Bellman–Ford 的其他优化除了队列优化SPFABellman–Ford 还有其他形式优化它们在部分图上效果明显但在某些特殊图上最坏复杂度可能达到指数级堆优化将队列换成堆与 Dijkstra 的区别是允许一个点多次入队在有负权边的图上可能被卡成指数级复杂度。栈优化将队列换成栈将 BFS 过程变成 DFS在寻找负环时可能效率更高但最坏时间复杂度仍为指数级。LLL 优化将普通队列换成双端队列每次将入队结点距离与队内距离平均值比较更大则插入队尾否则插入队首。SLF 优化将普通队列换成双端队列每次将入队结点距离与队首比较更大则插入队尾否则插入队首。D´Esopo–Pape 算法将普通队列换成双端队列若结点之前没入过队则插入队尾否则插入队首。Dijkstra 算法非负权图上的单源最短路Dijkstra 算法/ˈdikstrɑ/ 或 /ˈdɛikstrɑ/由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现、1959 年公开发表是求解非负权图单源最短路径的经典算法。过程将结点分成两个集合已确定最短路长度的点集 $S$ 与未确定的点集 $T$。初始所有点都属于 $T$初始化 $dis(s)0$其余点 $dis\infty$。随后重复从 $T$ 集合中选取最短路长度最小的结点移入 $S$ 集合对刚加入 $S$ 的结点的所有出边执行松弛操作。直到 $T$ 集合为空算法结束。时间复杂度分析朴素实现每次在 $T$ 中暴力寻找最小值。2 操作总代价 $O(m)$1 操作总代价 $O(n^2)$全过程的复杂度为 $O(n^2m)O(n^2)$。堆优化每成功松弛一条边 $(u,v)$ 就将 $v$ 插入堆若已在堆中则执行 Decrease-key1 操作直接取堆顶。共 $O(m)$ 次 Decrease-key、$O(n)$ 次 pop不同堆结构对应不同复杂度参考 堆 页面斐波那契堆等可做到最优的 $O(n\log n m)$。优先队列常用无法执行 Decrease-key改为每次松弛时重新插入该结点弹出时检查该结点是否已被松弛过是则跳过。复杂度 $O(m\log n)$优点是实现简单这也是比较表中默认的实现方式。线段树实现复杂度 $O(m\log n)$在一些特殊的非递归线段树实现下常数比堆更小且支持更多操作某些特殊图问题只能用线段树维护。选型建议稀疏图中 $mO(n)$堆优化 Dijkstra 效率优势明显稠密图中 $mO(n^2)$朴素实现更优。正确性证明数学归纳法下面证明在所有边权非负的前提下每次 1 操作取出的结点 $u$ 都满足 $D(u)dis(u)$。初始时 $S\varnothing$命题平凡成立。用反证法。设 $u$ 是第一个加入 $S$ 时不满足 $D(u)dis(u)$ 的点。由于 $s$ 一定满足且最先加入 $S$加入 $u$ 前 $S\neq\varnothing$若不存在 $s$ 到 $u$ 的路径则 $D(u)dis(u)\infty$矛盾。于是存在路径 $s\to x\to y\to u$其中 $y$ 是路径上第一个属于 $T$ 的点$x$ 是 $y$ 的前驱$x\in S$$sx$ 或 $yu$ 时对应空路径。因 $u$ 之前的点均满足 $Ddis$$x$ 加入 $S$ 时边 $(x,y)$ 会被松弛故 $u$ 加入时必有 $D(y)dis(y)$。路径上边权非负故 $D(y)\leq D(u)$于是 $dis(y)D(y)\leq D(u)\leq dis(u)$而 $u$ 被取出 $T$ 时 $y$ 尚未被取出故 $dis(u)\leq dis(y)$。两式结合得 $dis(y)D(y)D(u)dis(u)$与假设矛盾。关键边界证明中的关键不等式 $D(y)\leq D(u)$ 依赖边权非负。一旦图上存在负权边该不等式不再成立Dijkstra 可能给出错误结果。实现朴素实现$O(n^2)$ C cpp struct edge { int v, w; };vectoredge e[MAXN]; int dis[MAXN], vis[MAXN]; void dijkstra(int n, int s) { memset(dis, 0x3f, (n 1) * sizeof(int)); dis[s] 0; for (int i 1; i n; i) { int u 0, mind 0x3f3f3f3f; for (int j 1; j n; j) if (!vis[j] dis[j] mind) u j, mind dis[j]; vis[u] true; for (auto ed : e[u]) { int v ed.v, w ed.w; if (dis[v] dis[u] w) dis[v] dis[u] w; } } } Python python class Edge: def __init(self, v0, w0): self.v v self.w we [[Edge() for i in range(MAXN)] for j in range(MAXN)] INF 0x3F3F3F3F def dijkstra(n, s): dis [INF] * (n 1) vis [0] * (n 1) dis[s] 0 for i in range(1, n 1): u 0 mind INF for j in range(1, n 1): if not vis[j] and dis[j] mind: u j mind dis[j] vis[u] True for ed in e[u]: v, w ed.v, ed.w if dis[v] dis[u] w: dis[v] dis[u] w 优先队列实现$O(m\log m)$ C cpp struct edge { int v, w; };struct node { int dis, u; bool operator(const node a) const { return dis a.dis; } }; vectoredge e[MAXN]; int dis[MAXN], vis[MAXN]; priority_queuenode, vectornode, greaternode q; void dijkstra(int n, int s) { memset(dis, 0x3f, (n 1) * sizeof(int)); memset(vis, 0, (n 1) * sizeof(int)); dis[s] 0; q.push({0, s}); while (!q.empty()) { int u q.top().u; q.pop(); if (vis[u]) continue; // 惰性删除弹出时检查是否已确定 vis[u] 1; for (auto ed : e[u]) { int v ed.v, w ed.w; if (dis[v] dis[u] w) { dis[v] dis[u] w; q.push({dis[v], v}); } } } } Pythonpython def dijkstra(e, s): 输入 e:邻接表 s:起点 返回 dis:从s到每个顶点的最短路长度 dis defaultdict(lambda: float(inf)) dis[s] 0 q [(0, s)] vis set() while q: _, u heapq.heappop(q) if u in vis: continue vis.add(u) for v, w in e[u]: if dis[v] dis[u] w: dis[v] dis[u] w heapq.heappush(q, (dis[v], v)) return dis优先队列实现使用惰性删除技巧同一结点可能被多次压入堆弹出时通过vis标记跳过已确定最短路的旧记录从而绕过优先队列不支持 Decrease-key 的限制。Johnson 全源最短路径算法任意图上的 DijkstraJohnson 算法和 Floyd 一样能求出无负环图上任意两点间的最短路径由 Donald B. Johnson 于 1977 年提出。动机任意两点最短路可以枚举起点跑 $n$ 次 Bellman–Ford$O(n^2m)$或直接用 Floyd$O(n^3)$。由于堆优化 Dijkstra 的单源复杂度优于 Bellman–Ford若能跑 $n$ 次 Dijkstra则总复杂度为 $O(nm\log m)$取决于实现优于跑 $n$ 次 Bellman–Ford且在稀疏图上优于 Floyd。但 Dijkstra 不能处理负权边因此需要预处理让所有边权非负。为什么简单的「整体加正数」不行一种朴素想法是给所有边同时加上正数 $x$使边权非负若新图上最短路经过 $k$ 条边减去 $kx$ 即可还原。但这是错误的——考虑下图原图其中 $1\to 2$ 的最短路为 $1\to 5\to 3\to 2$长度为 $-2$。假如把每条边的边权加上 $5$新图上 $1\to 2$ 的最短路变为 $1\to 4\to 2$已经不再是实际的最短路——因为整体加权使经过边数更多的路径受到更大惩罚改变了路径的相对优劣。Johnson 的重新标号方法新建虚拟结点编号设为 $0$从它向其他所有点连一条边权为 $0$ 的边用 Bellman–Ford 求从 $0$ 号点到其他所有点的最短路记为 $h_i$对每条边 $u\to v$原边权 $w$重新设置边权为 $wh_u-h_v$以每个点为起点跑 $n$ 轮 Dijkstra 即可求出任意两点最短路。时间复杂度初始的 Bellman–Ford 不是瓶颈用priority_queue实现 Dijkstra 时总复杂度为 $O(nm\log m)$。正确性证明势能视角为什么重新标号是正确的先回顾物理中的势能概念重力势能、电势能等势能的变化量只与起点和终点的相对位置有关与所走路径无关势能的绝对值取决于零势能点的选取但两点间势能的差值是一定的。回到图中在重新标记后的图上从 $s$ 到 $t$ 的路径 $s\to p_1\to p_2\to\dots\to p_k\to t$ 的长度为 $$ (w(s,p_1)h_s-h_{p_1})(w(p_1,p_2)h_{p_1}-h_{p_2})\dots(w(p_k,t)h_{p_k}-h_t) $$ 化简得 $$ w(s,p_1)w(p_1,p_2)\dotsw(p_k,t)h_s-h_t $$ 无论走哪条路径$h_s-h_t$ 恒定不变——这正是势能的性质。因此把 $h_i$ 称为 $i$ 点的势能。新图上 $s\to t$ 的最短路长度由「原图最短路」与「两点势能差」两部分构成势能差为定值故原图最短路与新图最短路一一对应。证明还未完成还需说明新图中所有边权非负否则 Dijkstra 的正确性无法保证。根据三角形不等式图上任意边 $(u,v)$ 满足 $h_v\leq h_uw(u,v)$因此该边重新标记后的边权 $$ w(u,v)w(u,v)h_u-h_v\geq 0 $$ 由此可知新图边权均非负Johnson 算法得证。不同最短路算法的横向比较最短路算法FloydBellman–FordDijkstraJohnson最短路类型每对结点之间的最短路单源最短路单源最短路每对结点之间的最短路作用于任意图任意图非负权图任意图能否检测负环能能不能能时间复杂度$O(N^3)$$O(NM)$$O(M\log M)$$O(NM\log M)$注表中 Dijkstra 的复杂度均按priority_queue实现计算。选型速查需要全源最短路且 $n$ 较小约 $n\leq 400$→ 用 Floyd实现最简单需要全源最短路且图较大、可能有负权边 → 用 Johnson稀疏图上明显优于 Floyd单源最短路、边权非负→ 用 Dijkstra稠密图用朴素实现稀疏图用堆优化单源最短路、存在负权边或需要判负环→ 用 Bellman–Ford / SPFA。输出最短路径方案开一个pre数组在更新距离时记录下「从哪个前驱转移过来」算法结束后递归输出即可Floyd记录pre[i][j] k中间点回溯时拼接Bellman–Ford / Dijkstra一般记录pre[v] u前驱结点从终点沿pre反推至源点。特殊情形的变体算法边权只由 $0$ 和 $1$ 组成的图求最短路可用 0-1 BFS双端队列 BFS。其思路是在普通 BFS 基础上用deque维护遇到 $0$ 权边插队首、$1$ 权边插队尾从而以 $O(nm)$ 的代价求最短路。允许至多 $k$ 次改变路径成本如免费通过 $k$ 条边的最短路问题可用 分层图最短路。将图复制为 $k1$ 层设 $dis_{i,j}$ 表示从起点到 $i$ 号结点、已使用 $j$ 次免费权限后的最短路层间转移对应使用免费权限的操作最后在普通最短路框架如 Dijkstra上求解。参考资料《算法导论第 3 版中译本》机械工业出版社2013 年第 384–385 页Dijkstra 正确性证明参考。本文核心内容整理自 OI-wiki 的 最短路 章节算法实现与仓库内 docs/graph/min-cycle.md、docs/graph/code/mod-shortest-path/mod-shortest-path_1.cpp、docs/graph/code/diff-constraints/diff-constraints_1.cpp 等源码与页面相互印证。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考