Appearance
最短路径：Dijkstra 与 Floyd
概念
最短路径问题分两类：
| 类型 | 问题 | 代表算法 |
|---|---|---|
| 单源最短路径 | 从一个源点到其余所有点的最短路径 | Dijkstra（迪杰斯特拉） |
| 所有顶点对 | 任意两点之间的最短路径 | Floyd（弗洛伊德） |
一句话理解：最小生成树关心"把所有点连起来的总代价最小"（全局 n − 1 条边），最短路径关心"从 A 到 B 单独一条路径最短"（局部最优路线）。两者长得像，但不是一回事。
（无权值图的最短路）已在 BFS 一章解决——按层扩散即可。本章处理带权值的情况。
原理
Dijkstra：按距离由近到远"确定下来"
核心前提是所有权值非负。在此条件下有一个关键性质：
当前未确定顶点中 dist 最小的那个 u，它的 dist 已经是最终最短距离，可以永久确定进集合 S。
理由：任何经由别的未确定顶点 x 转去 u 的路线，都要先付出 dist[x] ≥ dist[u] 的代价，不可能比直接到 u 更短（因为边权非负）。
Dijkstra(G, s):
dist[s] = 0; 其余 dist = ∞
S = {} /* 已确定最终距离的集合 */
重复 n 次:
u = argmin{ dist[v] | v ∉ S } /* O(n) 扫描 */
S ∪= {u}
for 每条以 u 为尾的弧 <u, v, w>: /* 松弛 */
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w; path[v] = upath[v]记录最短路上的前驱，可回溯出完整路径。- 数组版外层 n 次、每次扫 n 个 →
- 408 默认考数组版 O(n²)。
Dijkstra 不能处理负权边
上面"不可能更短"的推理依赖 边权非负。一旦有负权边，先被确定的顶点之后可能被更小的路径反超，而 S 中的顶点不会再被更新 → 结果错误。负权图要用 Bellman-Ford。
反例：1→2 权 2，1→3 权 3，3→2 权 −2。真实最短的 1→2 是 1→3→2 = 1；但 Dijkstra 在第 2 轮就"确定"了 dist[2] = 2，之后即使按个点到 3 也不会回头修正它。
Floyd：逐个放开中转点
设
含义：允许 k 作为中转点后，要么不用它（保持原值），要么走 i → k → j。把 k 从 1 枚举到 n，最后
Floyd(A):
D = A 的副本 /* D[i][i] = 0，无边为 ∞ */
for k = 1..n:
for i = 1..n:
for j = 1..n:
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
P[i][j] = P[k][j] /* j 在路径上的前驱跟着改 */- 三重循环，固定
- 可以多次原地更新（
- 允许负权边，但图中不能存在负权回路（否则最短路无定义，距离可以无限小）。
P[i][j]记录 i→j 最短路径上 j 的直接前驱，据此递归还原整条路径。
两者对比
| Dijkstra | Floyd | |
|---|---|---|
| 求什么 | 单源到所有点的距离 | 任意两点间距离 |
| 复杂度 | ||
| 适合存储 | 邻接矩阵（数组版） | 必须用邻接矩阵 |
| 负权边 | 不允许 | 允许（但不能有负权回路） |
| 适合规模 | 稀疏图、只要一个源点 | 稠密图、要求所有点对 |
示例
例 1：Dijkstra（从顶点 1 出发）
沿用第 22 章那张带权无向图：
(1,2)=6 (1,3)=1 (2,4)=5 (2,5)=3 (3,5)=7 (4,6)=2 (5,6)=6
6 5
1 ──────── 2 ──────── 4
│1 ╲ │ ╲ │2
│ 3 │ ╲ │
3 ──────── 5 ──────── 6
7 6逐步推演（∞ 记作 —）：
| 轮次 | dist 状态（1,2,3,4,5,6） | 选出的 u | 本轮松弛（成功更新的） | S |
|---|---|---|---|---|
| 初始 | 0, —, —, —, —, — | 1 (0) | 2→6，3→1 | |
| 2 | 0, 6, 1, —, —, — | 3 (1) | 5→1+7=8 | |
| 3 | 0, 6, 1, —, 8, — | 2 (6) | 4→6+5=11 | |
| 4 | 0, 6, 1, 11, 8, — | 5 (8) | 6→8+6=14 | |
| 5 | 0, 6, 1, 11, 8, 14 | 4 (11) | 6→11+2=13（比 14 小，覆盖） | |
| 6 | 0, 6, 1, 11, 8, 13 | 6 (13) | 无 | 全部 |
最终结果：
dist[1..6] = 0, 6, 1, 11, 8, 13
到 6 的最短路：1 → 2 → 4 → 6，长度 6 + 5 + 2 = 13
（另一条 1→3→5→6 = 1 + 7 + 6 = 14，更长）关键细节：第 5 轮之前 dist[6] 已经被更新成 14（经 5），但那时还没轮到 4；轮到 4 时发现 11 + 2 = 13 更短，于是覆盖。可见 dist 可以多次被松弛，只有进 S 的那一刻才是最终值。
例 2：Floyd（4 个顶点的有向图）
有向图四条顶点，弧为：
1→2=5, 1→3=9, 2→3=2, 2→4=7, 3→4=1, 4→1=3
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 5 | 9 | ∞ |
| 2 | ∞ | 0 | 2 | 7 |
| 3 | ∞ | ∞ | 0 | 1 |
| 4 | 3 | ∞ | ∞ | 0 |
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 5 | 9 | ∞ |
| 2 | ∞ | 0 | 2 | 7 |
| 3 | ∞ | ∞ | 0 | 1 |
| 4 | 3 | 8 | 12 | 0 |
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 5 | 7 | 12 |
| 2 | ∞ | 0 | 2 | 7 |
| 3 | ∞ | ∞ | 0 | 1 |
| 4 | 3 | 8 | 10 | 0 |
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 5 | 7 | 8 |
| 2 | ∞ | 0 | 2 | 3 |
| 3 | ∞ | ∞ | 0 | 1 |
| 4 | 3 | 8 | 10 | 0 |
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 5 | 7 | 8 |
| 2 | 6 | 0 | 2 | 3 |
| 3 | 4 | 9 | 0 | 1 |
| 4 | 3 | 8 | 10 | 0 |
路径矩阵 P（P[i][j] = i→j 最短路上 j 的直接前驱，− 表示 i = j）：
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | − | 1 | 2 | 3 |
| 2 | 4 | − | 2 | 3 |
| 3 | 4 | 1 | − | 3 |
| 4 | 4 | 1 | 2 | − |
还原路径示例（2 → 1，距离 6）：
P[2][1] = 4 → 2 ... → 4 → 1
P[2][4] = 3 → 2 ... → 3 → 4 → 1
P[2][3] = 2 → 2 → 3 → 4 → 1
把每段往左接起来读出：**2 → 3 → 4 → 1**，权值 2 + 1 + 3 = 6 ✓C 语言：Dijkstra + Floyd
#include <stdio.h>
#define MAXV 10
#define INF 0x3f3f3f3f
int n = 6, g[MAXV][MAXV]; /* 邻接矩阵 */
int dist[MAXV], path[MAXV], S[MAXV];
/* Dijkstra：数组版 O(n^2)，权值必须非负 */
void dijkstra(int s) {
int i, j, u;
for (i = 0; i < n; i++) {
dist[i] = g[s][i];
path[i] = (g[s][i] < INF) ? s : -1;
S[i] = 0;
}
S[s] = 1; dist[s] = 0; path[s] = -1;
for (int round = 1; round < n; round++) {
int min = INF; u = -1;
for (j = 0; j < n; j++) /* 找未确定中 dist 最小者 */
if (!S[j] && dist[j] < min) { min = dist[j]; u = j; }
if (u < 0) break;
S[u] = 1;
for (j = 0; j < n; j++) /* 用 u 松弛它的出边 */
if (!S[j] && g[u][j] < INF && dist[u] + g[u][j] < dist[j]) {
dist[j] = dist[u] + g[u][j];
path[j] = u;
}
}
}
void printPath(int s, int t) {
int stack[MAXV], top = 0, v = t;
while (v != -1) { stack[top++] = v; v = (v == s) ? -1 : path[v]; }
for (int i = top - 1; i >= 0; i--) printf("%d%s", stack[i] + 1, i ? " -> " : "");
}
/* Floyd：O(n^3)，D 会被原地更新成最终结果 */
void floyd(int D[MAXV][MAXV], int P[MAXV][MAXV]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
P[i][j] = (i != j && D[i][j] < INF) ? i : -1;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (D[i][k] < INF && D[k][j] < INF && D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];
P[i][j] = P[k][j];
}
}
int main(void) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) g[i][j] = (i == j) ? 0 : INF;
int E[][3] = { {1,2,6},{1,3,1},{2,4,5},{2,5,3},{3,5,7},{4,6,2},{5,6,6} };
for (int i = 0; i < 7; i++) {
int u = E[i][0]-1, v = E[i][1]-1, w = E[i][2];
g[u][v] = g[v][u] = w; /* 无向图 = 两条对称弧 */
}
dijkstra(0);
for (int i = 0; i < n; i++) printf("1 -> %d : dist = %d 路径 ", i + 1, dist[i]), printPath(0, i), printf("\n");
/* 1->1:0 1->2:6 1->3:1 1->4:11 1->5:8 1->6:13 */
/* Floyd 用另一张 4 点有向图演示 */
n = 4;
int D[MAXV][MAXV], P[MAXV][MAXV];
int arcs[][3] = { {1,2,5},{1,3,9},{2,3,2},{2,4,7},{3,4,1},{4,1,3} };
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) D[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < 6; i++) D[arcs[i][0]-1][arcs[i][1]-1] = arcs[i][2];
floyd(D, P);
printf("\nFloyd 结果矩阵：\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) printf("%4d", D[i][j] > INF / 2 ? -1 : D[i][j]);
printf("\n");
}
printf("P[2][1] = %d（2 到 1 的最短路上 1 的前驱）\n", P[1][0] + 1); /* 4 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
import heapq
INF = float('inf')
# ---------- Dijkstra ----------
E = [(1,2,6),(1,3,1),(2,4,5),(2,5,3),(3,5,7),(4,6,2),(5,6,6)]
n = 6
adj = {i: [] for i in range(1, n + 1)}
for u, v, w in E:
adj[u].append((v, w)); adj[v].append((u, w))
def dijkstra(s):
"""堆优化版 O(e log n)，便于看清 dist 被反复松弛"""
dist = {i: INF for i in adj}; dist[s] = 0
prev = {i: None for i in adj}
pq = [(0, s)]; done = set()
while pq:
d, u = heapq.heappop(pq)
if u in done: continue # 陈旧条目，跳过
done.add(u)
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w; prev[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, prev
def build_path(prev, s, t):
p = [t]
while t != s:
t = prev[t]; p.append(t)
return list(reversed(p))
dist, prev = dijkstra(1)
print("dist:", dist) # {1:0, 2:6, 3:1, 4:11, 5:8, 6:13}
print("1 -> 6 最短路:", build_path(prev, 1, 6), " 长度:", dist[6]) # [1,2,4,6] 13
# ---------- Floyd ----------
V = [1, 2, 3, 4]
arcs = [(1,2,5),(1,3,9),(2,3,2),(2,4,7),(3,4,1),(4,1,3)]
D = [[0 if i == j else INF for j in V] for i in V]
P = [[None]*4 for _ in V]
for u, v, w in arcs:
D[u-1][v-1] = w; P[u-1][v-1] = u
def show(M):
for row in M:
print(["INF" if x == INF else str(x) for x in row])
print("\nD(-1):"); show(D)
for k in range(4): # 逐个放开中转点 1..4
for i in range(4):
for j in range(4):
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
P[i][j] = P[k][j]
print("D(%d):" % (k + 1)); show(D)
def floyd_path(P, i, j):
if i == j: return [i]
return floyd_path(P, i, P[i-1][j-1]) + [j]
print("\n2 -> 1 最短路:", floyd_path(P, 2, 1), " 长度:", D[1][0]) # [2,3,4,1] 6
print("3 -> 2 最短路:", floyd_path(P, 3, 2), " 长度:", D[2][1]) # [3,4,1,2] 9
# ---------- Dijkstra 遇负权失效 ----------
# 图：1->2 = 2，1->3 = 3，3->2 = -2
bad = {1: [(2, 2), (3, 3)], 2: [], 3: [(2, -2)]}
def dijkstra_strict(g, s):
"""教科书版 Dijkstra：进了 S 的顶点不再被松弛"""
d = {i: INF for i in g}; d[s] = 0
done = set()
for _ in range(len(g)):
u = min((v for v in g if v not in done), key=lambda v: d[v])
done.add(u)
for v, w in g[u]:
if v not in done and d[u] + w < d[v]: # S 内的点不看
d[v] = d[u] + w
return d
print("\n负权图 Dijkstra 结果:", dijkstra_strict(bad, 1)) # {1: 0, 2: 2, 3: 3}
print("真实最短路 1->3->2 =", 3 + (-2), "，Dijkstra 给出 2 -> 失效")
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- Dijkstra：数组版
- Floyd：
- Dijkstra 的松弛式
- Floyd 的递推：
- 无权图（或所有权相等的图）的单源最短路 → BFS 即可，不必上 Dijkstra。
2. 解题套路
- 手算 Dijkstra：画一张"dist 状态"表，每轮选当前 dist 最小的顶点进 S，再用它松弛尚未进 S 的邻居。已在 S 中的顶点不再被更新，这是算法成立的前提。
- 手算 Floyd：先抄初始矩阵，然后 k = 1..n 一遍一遍描新矩阵，第 k 遍只允许"经 ≤ k 号顶点"中转。把每遍矩阵都写出来不容易错。
- 问"某条最短路径经过哪些点"：Dijkstra 看 path[] 回溯；Floyd 看 P 矩阵，从 P[i][j] 递归回溯。
3. 易错点
- Floyd 的循环顺序必须是 k 在外，i、j 在内。写成 i 在外就变成"单趟扫描"，结果错误。这是 Floyd 最经典的填空陷阱。
- 认为 Dijkstra 能处理负权。不能。负权要去用 Bellman-Ford。
- 把 MST 的 Prim 和 Dijkstra 混为一谈：Prim 更新的是"到集合 U 的最小边权"，Dijkstra 更新的是"到源点的最短（累加）距离"。
- Floyd 的
- Dijkstra 中"dist 已确定"指的是该顶点已经并入 S；在并入之前它的 dist 还会被反复改写（本例中的顶点 6 就被改过一次：14 → 13）。
- 有向图建矩阵时，不能顺手把
g[v][u]也填上，那会把有向图变成无向图。
小结
- Dijkstra 单源
- Floyd 全源
- Dijkstra 不许负权；Floyd 允许负权但不允许负权回路（用
- 路径输出靠前驱：Dijkstra 用 path[]，Floyd 用 P 矩阵递归回溯。
- 下一步：以上都是无环依赖无关的路径问题，若给的是"谁必须先于谁"的偏序关系，就要做拓扑排序。
下一篇：拓扑排序
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。