最短路径问题是图论中最经典、应用最广的问题之一。简单说，就是给定一个图（由点和带权边组成），要找到任意两点之间总权重最小的路径。
一个很常见的现实案例，是导航软件是如何计算出两地之间最快的路线的。这就是在求解最短路径问题。理解这个问题的不同场景，是学习算法的第一步。
- 单源最短路径：求从图中的一个特定起点到所有其他点的最短路径。
- 多源（全源）最短路径：求图中任意两点之间的最短路径。
- 确定终点：在无向图中与单源问题一致；在有向图中，可以通过反转所有边的方向转化为单源问题。
在深入细节前，可以先通过这个表格对四大基础算法有个整体把握：
| 算法 | 类型 | 时间复杂度 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|---|---|
| BFS | 单源 | O(N + M) | 边权相等图 | 速度快，实现简单 | 无法处理带权图 |
| Floyd | 多源 | O(N³) | 稠密图、小规模 | 实现极其简单 | 时间复杂度高 |
| Dijkstra | 单源 | 朴素O(N²) 堆优化O(M log N) | 非负权图 | 高效，稳定 | 无法处理负权边 |
| Bellman-Ford | 单源 | O(N * M) | 有负权边 | 可检测负环 | 效率较低 |
| SPFA | 单源 | 平均O(M)，最坏O(N*M) | 稀疏图、有负权 | 通常较快 | 不稳定，易被卡 |
| Johnson | 全源 | O(N * M * log N) | 稀疏图、有负权 | 结合Bellman-Ford和Dijkstra的优点 | 实现相对复杂 |
| A* | 单源（启发式） | 视启发函数而定 | 有目标、有估计 | 高效，常用于路径规划 | 需要设计启发函数 |
| 双向搜索 | 单源（特定） | 视算法而定 | 边权相等图、起点终点明确 | 大幅减少搜索空间 | 实现稍复杂 |
一、基础筑基 (Foundation)
1. DFS/BFS (适用：无权图/边权为1)
当图中所有边的权值相等（通常为1），即寻找跳数最少的路径时，最直接的方法就是广度优先搜索 (BFS)。BFS的特性确保了第一次访问到某个节点时，所经过的路径就是最短的。
代码模板：
#include <bits/stdc++.h>
using namespace std;
vector<int> bfsShortestPath(vector<vector<int>>& graph, int start, int end) {
int n = graph.size();
vector<int> dist(n, -1), prev(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == end) break; // 找到目标，提前退出
for (int v : graph[u]) {
if (dist[v] == -1) { // 未访问过
dist[v] = dist[u] + 1;
prev[v] = u;
q.push(v);
}
}
}
// 构建路径
vector<int> path;
for (int at = end; at != -1; at = prev[at]) path.push_back(at);
reverse(path.begin(), path.end());
return path;
}推荐习题：牛妹的苹果树
2. Floyd算法
Floyd算法（弗洛伊德算法）采用动态规划思想，求解任意两点间的最短路径。它的核心是“插点法”：逐步允许每个顶点作为中转点，检查是否能缩短两点间的距离。
实现代码：
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f; // 用一个很大的数表示“无穷大”
int dist[510][510]; // 邻接矩阵存储距离
void floyd(int n) {
for (int k = 1; k <= n; k++) // 枚举中间点
for (int i = 1; i <= n; i++) // 枚举起点
for (int j = 1; j <= n; j++) // 枚举终点
if (dist[i][k] < INF && dist[k][j] < INF) // 防止溢出
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
int main() {
int n, m;
cin >> n >> m;
// 初始化邻接矩阵
memset(dist, 0x3f, sizeof(dist));
for (int i = 1; i <= n; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w); // 防止重边
}
floyd(n);
// 输出结果...
return 0;
}习题推荐：P2910 [USACO08OPEN] Clear And Present Danger S – 洛谷
一、单源正权之王
1. Dijkstra算法
Dijkstra算法（迪杰斯特拉算法）是解决非负权图单源最短路问题的首选。它采用贪心策略：维护一个“已确定最短路径”的集合，每次从“未确定”集合中选出一个距离源点最近的点，加入“已确定”集合并尝试用它去松弛其邻居的距离。
这是竞赛中最常用的写法，使用链式前向星存图，效率很高：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, int>;
const int N = 1e5 + 10, M = 2e5 + 10; // 根据题目调整大小
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s;
int head[N], cnt;
ll dist[N];
bool vis[N];
struct Edge {
int to, nxt;
ll w;
} e[M];
void addEdge(int u, int v, ll w) {
e[++cnt] = {v, head[u], w};
head[u] = cnt;
}
void dijkstra(int s) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq; // 小根堆
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
ll w = e[i].w;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v}); // 将更新后的节点加入堆
}
}
}
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v; ll w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++) cout << dist[i] << " \n"[i == n];
return 0;
}推荐习题：
P3371 【模板】单源最短路径（弱化版） – 洛谷
P4779 【模板】单源最短路径（标准版） – 洛谷
三、拥抱负权
1. Bellman-Ford算法
当图中存在负权边时，Dijkstra就失效了。Bellman-Ford算法（贝尔曼-福特算法）通过反复对所有边进行“松弛”操作来寻找最短路径。它是最通用的单源最短路算法，并能检测负权环（一种不存在最短路径的图）。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
};
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
vector<Edge> edges;
int dist[N];
bool bellmanFord(int n, int m, int s) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
// 最多松弛 n-1 次
for (int i = 1; i < n; i++) {
bool updated = false;
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
if (!updated) break; // 若本轮没有更新，则提前结束
}
// 第 n 次松弛，用于检测负环
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
return true; // 存在负环
}
}
return false; // 无负环
}2. SPFA算法
SPFA (Shortest Path Faster Algorithm) 是Bellman-Ford算法的队列优化版本。它只对“距离被更新过”的节点进行松弛，平均情况下效率很高，但在极端数据下可能退化。
实现代码如下：
SPFA (Shortest Path Faster Algorithm) 是Bellman-Ford算法的队列优化版本。它只对“距离被更新过”的节点进行松弛，平均情况下效率很高，但在极端数据下可能退化。推荐习题：
