OI-wiki 最短路算法完全指南：Floyd、Bellman–Ford、Dijkstra 与 Johnson 全解析-平芜编程栈

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$ 依次扩大问题规模）：

=== "C++"cpp 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]); } } }

=== "Python"python 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])

第一维的省略与证明

因为第一维对结果无影响，可以直接省略，得到空间优化版：

=== "C++"cpp 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]); } } }

=== "Python"python 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 外层循环枚举到 $k=u$ 之前，用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$，则在枚举到 $k=w$ 时环长即为 $dis_{u,v}+val(v,w)+val(w,u)$。该页同时给出了求最小环的完整 C++/Python 参考实现。

应用二：传递闭包

已知一个有向图中任意两点之间是否有连边，判断任意两点是否连通。

该问题即为求图的传递闭包。只需按照 Floyd 的过程逐个加入点判断：此时边权简化为 $1/0$，取min运算变成或运算。再用bitset优化，复杂度可降至 $O(\frac{n^3}{w})$：

// std::bitset<SIZE> 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; };

vector<Edge> 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, u=0, v=0, w=0): self.u = u self.v = v self.w = w

INF = 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 的点引出的边不可能发生松弛（无穷大与常数加减仍为无穷大），跳过可避免无意义的计算。

队列优化：SPFA

SPFA（Shortest Path Faster Algorithm）的核心观察是：只有上一次被松弛的结点所连接的边，才有可能引起下一次松弛操作。因此用队列维护「哪些结点可能引起松弛」，就能只访问必要的边。

SPFA 同样可以判断 $s$ 点能否抵达负环：记录最短路经过的边数cnt，当某点最短路边数达到至少 $n$ 时，说明经过了负环。

=== "C++" ```cpp struct edge { int v, w; };

vector<edge> e[MAXN]; int dis[MAXN], cnt[MAXN], vis[MAXN]; queue<int> 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 deque

class Edge: def __init__(self, v=0, w=0): 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 的其他优化

除了队列优化（SPFA），Bellman–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^2+m)=O(n^2)$。
堆优化：每成功松弛一条边 $(u,v)$ 就将 $v$ 插入堆（若已在堆中则执行 Decrease-key），1 操作直接取堆顶。共 $O(m)$ 次 Decrease-key、$O(n)$ 次 pop，不同堆结构对应不同复杂度（参考堆页面），斐波那契堆等可做到最优的 $O(n\log n + m)$。
优先队列（常用）：无法执行 Decrease-key，改为每次松弛时重新插入该结点，弹出时检查该结点是否已被松弛过，是则跳过。复杂度 $O(m\log n)$，优点是实现简单（这也是比较表中默认的实现方式）。
线段树实现：复杂度 $O(m\log n)$，在一些特殊的非递归线段树实现下常数比堆更小，且支持更多操作，某些特殊图问题只能用线段树维护。
选型建议：稀疏图中 $m=O(n)$，堆优化 Dijkstra 效率优势明显；稠密图中 $m=O(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$；$s=x$ 或 $y=u$ 时对应空路径）。
因 $u$ 之前的点均满足 $D=dis$，$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; };

vector<edge> 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, v=0, w=0): self.v = v self.w = w

e = [[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; } }; vector<edge> e[MAXN]; int dis[MAXN], vis[MAXN]; priority_queue<node, vector<node>, greater<node>> 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}); } } } } ```

=== "Python"python 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 全源最短路径算法：任意图上的 Dijkstra

Johnson 算法和 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$），重新设置边权为 $w+h_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)+\dots+w(p_k,t)+h_s-h_t $$ 无论走哪条路径，$h_s-h_t$ 恒定不变——这正是势能的性质。因此把 $h_i$ 称为 $i$ 点的势能。新图上 $s\to t$ 的最短路长度由「原图最短路」与「两点势能差」两部分构成，势能差为定值，故原图最短路与新图最短路一一对应。

证明还未完成：还需说明新图中所有边权非负，否则 Dijkstra 的正确性无法保证。根据三角形不等式，图上任意边 $(u,v)$ 满足 $h_v\leq h_u+w(u,v)$，因此该边重新标记后的边权 $$ w'(u,v)=w(u,v)+h_u-h_v\geq 0 $$ 由此可知新图边权均非负，Johnson 算法得证。

不同最短路算法的横向比较

最短路算法	Floyd	Bellman–Ford	Dijkstra	Johnson
最短路类型	每对结点之间的最短路	单源最短路	单源最短路	每对结点之间的最短路
作用于	任意图	任意图	非负权图	任意图
能否检测负环？	能	能	不能	能
时间复杂度	$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(n+m)$ 的代价求最短路。
允许至多 $k$ 次改变路径成本（如免费通过 $k$ 条边）的最短路问题：可用分层图最短路。将图复制为 $k+1$ 层，设 $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），仅供参考