flowchart TD
A[最短路问题] --> B{需要全源最短路?}
B -->|是| C{图是否稠密?}
B -->|否| D{存在负权边?}
C -->|"稠密图 m≈n²"| E["Floyd O(n³)"]
C -->|"稀疏图 m≈n"| F{存在负权边?}
F -->|否| G["n 次 Dijkstra O(nm log m)"]
F -->|是| H["Johnson O(nm log m)"]
D -->|否| I["Dijkstra O(m log m)"]
D -->|是| J{需要检测负环?}
J -->|是| K["Bellman-Ford O(nm)"]
J -->|否| L{图有特殊结构?}
L -->|随机图| M[SPFA 通常较快]
L -->|可能被卡| K
style I fill:#90EE90
style E fill:#87CEEB
style K fill:#FFB6C1
style H fill:#DDA0DD
快速选择
无负权边 + 单源：Dijkstra（最常用）
有负权边 / 判负环：Bellman-Ford
全源 + 稠密图：Floyd
全源 + 稀疏图 + 有负权：Johnson
记号
为了方便叙述，这里先给出下文将会用到的一些记号的含义。
n 为图上点的数目，m 为图上边的数目；
s 为最短路的源点；
D(u) 为 s 点到 u 点的 实际 最短路长度；
dis(u) 为 s 点到 u 点的 估计 最短路长度。任何时候都有 dis(u)≥D(u)。特别地，当最短路算法终止时，应有 dis(u)=D(u)。
w(u,v) 为 (u,v) 这一条边的边权。
性质
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。
对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。
对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 n，边数不会超过 n−1。
Floyd 算法
是用来求任意两个结点之间的最短路的。
复杂度比较高，但是常数小，容易实现（只有三个 for）。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
实现
我们定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k（也就是说，在子图 V′=1,2,…,k 中的路径，注意，x 与 y 不一定在这个子图中），结点 x 到结点 y 的最短路长度。
很显然，f[n][x][y] 就是结点 x 到结点 y 的最短路长度（因为 V′=1,2,…,n 即为 V 本身，其表示的最短路径就是所求路径）。
接下来考虑如何求出 f 数组的值。
f[0][x][y]：x 与 y 的边权，或者 0，或者 +∞（f[0][x][y] 什么时候应该是 +∞？当 x 与 y 间有直接相连的边的时候，为它们的边权；当 x=y 的时候为零，因为到本身的距离为零；当 x 与 y 没有直接相连的边的时候，为 +∞）。
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 点的最短路）。
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
class Edge: def __init__(self, u=0, v=0, w=0): self.u = u self.v = v self.w = wINF = 0x3F3F3F3Fedge = []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
队列优化：SPFA
即 Shortest Path Faster Algorithm。
很多时候我们并不需要那么多无用的松弛操作。
很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。
那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。
SPFA 也可以用于判断 s 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 n 条边时，说明 s 点可以抵达一个负环。
为什么 n 条边意味着负环？
一条不经过重复节点的路径，最多经过 n−1 条边（连接 n 个不同节点）
如果最短路需要 ≥n 条边，则路径上必有重复节点，即存在环
这个环能让路径变短（否则不会被松弛），所以是负环
实现
[list2tab]
C++
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
from collections import dequeclass Edge: def __init__(self, v=0, w=0): self.v = v self.w = we = [[Edge() for i in range(MAXN)] for j in range(MAXN)]INF = 0x3F3F3F3Fdef 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
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
class Edge: def __init(self, v=0, w=0): self.v = v self.w = we = [[Edge() for i in range(MAXN)] for j in range(MAXN)]INF = 0x3F3F3F3Fdef 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
[!note] 优先队列实现（推荐）
[list2tab]
C++
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}); // 注意：同一个点可能多次入队 } } }}
