最短路径问题详解：Dijkstra 与 Floyd

在图论中，最短路径问题主要分为两类：

  1. 单源最短路径 (Single-Source Shortest Path)：求从一个起点到其他所有点的最短路径。（代表：Dijkstra）
  2. 多源最短路径 (All-Pairs Shortest Path)：求任意两个点之间的最短路径。（代表：Floyd）

一、Dijkstra 算法 (单源最短路)

适用场景：带权图（无向/有向），边权非负。
核心思想：贪心策略 (Greedy) + 广度优先搜索 (BFS) 的变种。

1. 详细思路：作为“涟漪”扩散

想象你站在起点 $S$，往地上倒了一桶水。水流会优先沿着阻力最小（边权最小）的路径蔓延。

  • 我们维护一个集合 $S$（已确定最短路的点）和一个集合 $U$（未确定最短路的点）。
  • 每次从 $U$ 中找出一个距离起点最近的点 $u$，把它加入 $S$。
  • 然后以 $u$ 为跳板，去“松弛” (Relax) 它的邻居 $v$。
    • 松弛操作：如果 dist[u] + weight(u, v) < dist[v]，说明通过 $u$ 到达 $v$ 比原来的路径更近，更新 dist[v]。

2. 算法步骤

  1. 初始化：
    • dist 数组：起点 dist[start] = 0，其余所有点 dist[i] = INF。
    • visited 数组：标记节点是否已确定最短路，初始全为 false。
    • 优先队列 pq：存入 {0, start}。
  2. 循环（直到队列为空）：
    • 弹出堆顶元素 {d, u}（距离最小的点）。
    • 如果 visited[u] 为 true，跳过（懒惰删除）。
    • 标记 visited[u] = true。
    • 扫描邻居：遍历 $u$ 的所有出边 $(u, v)$，权值为 $w$。
      • 若 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w，并将 {dist[v], v} 推入队列。

3. 代码模板 (堆优化版)

时间复杂度：$O(E \log V)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <vector>
#include <queue>
#include <functional>
using namespace std;

const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };

// 返回从 start 到所有点的最短距离数组
vector<int> dijkstra(int start, int n, const vector<vector<Edge>>& adj) {
    vector<int> dist(n + 1, INF);
    vector<bool> visited(n + 1, false);
    // 小根堆：pair<距离, 节点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int weight = edge.w;
            // 松弛操作
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
````

### 4. 常见考察形式

1. **手算题**：给出一个 5-6 个节点的图，要求列出每一步 `dist` 数组和 `visited` 集合的变化。
    
    - _技巧_：画一个表格，每一行代表选定一个节点后，其他节点距离的更新情况。
        
2. **负权边陷阱**：
    
    - _问_：Dijkstra 能处理负权边吗？
        
    - _答_：**不能**。因为 Dijkstra 假设一旦节点被标记为 visited，其最短路就确定了。负权边可能会打破这个假设。
        
3. **最短路径计数**：不仅求最短距离，还求有多少条最短路径。
    
    - _解法_：在松弛时维护一个 `count` 数组。如果 `dist[u]+w < dist[v]`，`count[v] = count[u]`；如果相等，`count[v] += count[u]`。
        

---

## 二、Floyd-Warshall 算法 (多源最短路)

适用场景：带权图，节点数较少 ($N \le 300$)，允许负权边（但不允许负权回路）。

核心思想：动态规划 (Dynamic Programming)。

### 1. 详细思路：中转点的艺术

Floyd 算法探讨的是：**如果我们允许经过节点 $1...k$ 作为中转站，节点 $i$ 到 $j$ 的最短路径会是多少？**

- 状态定义：$D[k][i][j]$ 表示“只允许经过节点 $1$ 到 $k$ 之间作为中间节点时，从 $i$ 到 $j$ 的最短路径”。
    
- 状态转移方程：
    
    $$D[k][i][j] = \min(D[k-1][i][j], \quad D[k-1][i][k] + D[k-1][k][j])$$
    
    - 含义：从 $i$ 到 $j$ 的路，要么不经过 $k$（保持原样），要么经过 $k$（$i \to k \to j$）。
        
- **空间优化**：由于 $k$ 状态只依赖于 $k-1$，可以将三维数组压缩为二维数组 `dist[i][j]`。
    

### 2. 算法步骤

1. **初始化**：
    
    - 二维矩阵 `dist[N][N]`。
        
    - `dist[i][i] = 0`。
        
    - 若 $i, j$ 有边，`dist[i][j] = weight`。
        
    - 若无边，`dist[i][j] = INF`。
        
2. **三重循环**（**最关键点**）：
    
    - 第一层循环枚举**中转点** $k$ (1 到 $n$)。
        
    - 第二层循环枚举**起点** $i$。
        
    - 第三层循环枚举**终点** $j$。
        
    - 更新：`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。
        

### 3. 代码模板

_时间复杂度：$O(N^3)$_

C++

```cpp
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

// 直接在 adj 矩阵上修改，运行后 adj[i][j] 即为最短路
void floyd(int n, vector<vector<int>>& adj) {
    // 1. 核心是 k 必须在最外层！！！
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 防止溢出：确保 i->k 和 k->j 都是可达的
                if (adj[i][k] != INF && adj[k][j] != INF) {
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
                }
            }
        }
    }
}

4. 常见考察形式

  1. 循环顺序（必考）：

    • 问：如果把 $k$ 放在最内层循环会怎样？

    • 答：算法会失效。因为 Floyd 的本质是 DP，$k$ 代表阶段。如果 $k$ 在内层，意味着你在计算 $i \to j$ 时，只考虑了某一个中转点，而不是逐步引入所有中转点。

  2. 传递闭包 (Transitive Closure)：

    • 问：如何判断图中任意两点 $i$ 和 $j$ 是否连通？

    • 解法：把 Floyd 中的 min 改为 || (OR)，+ 改为 && (AND)。

    • adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j])。

  3. 最小环问题：

    • Floyd 算法可以顺便求出图中的最小环（权值和最小的回路）。

三、两种算法对比总结

特性 Dijkstra (堆优化) Floyd-Warshall
解决问题 单源最短路 (1对多) 多源最短路 (多对多)
时间复杂度 $O(E \log V)$ $O(N^3)$
空间复杂度 $O(N)$ (存距离) $O(N^2)$ (邻接矩阵)
适用数据规模 $N \le 10^5$ (稀疏图) $N \le 400$ (稠密图)
负权边 不支持 支持 (不能有负环)
数据结构首选 邻接表 (vector<vector<Edge>>) 邻接矩阵 (vector<vector<int>>)
核心逻辑 贪心 (Greedy) 动态规划 (DP)

考试做题策略

  1. 看到 $N$ 很小 (<=300)，且问“任意两点间距离” -> Floyd。

  2. 看到 $N$ 很大 (1000+)，或者是“从某点出发” -> Dijkstra。

  3. 看到 边权为负 -> 排除 Dijkstra，如果是单源用 SPFA/Bellman-Ford，如果是多源且 $N$ 小用 Floyd。