最短路径问题
最短路径是图论的核心问题：在加权图中找两节点之间路径权值和最小的路径。按”起点数量”可分为单源（一个起点到所有点）和多源（任意两点间）两大类，按边权又分为非负权与含负权两类。选择正确算法是解这类题的第一步。
算法总览
| 算法 | 适用条件 | 时间复杂度 | 特点 |
|---|---|---|---|
| Dijkstra | 边权非负 | O((V+E) log V)（堆优化） | 单源，贪心思想，最常用 |
| Bellman-Ford | 允许负权边，不能有负权环 | O(V·E) | 单源，可检测负权环 |
| SPFA | 允许负权边 | 平均 O(E)，最坏 O(V·E) | Bellman-Ford 队列优化，慎用 |
| Floyd-Warshall | 任意权值（无负权环） | O(V³) | 多源，动态规划，代码极简 |
Dijkstra：非负权单源最短路径
贪心策略：每次从未确定最短路的节点中，选择距离起点最近的一个”确认”下来（因为边权非负，它不可能再被其他路径更新得更短），然后松弛它的所有出边。用优先队列加速”取最近节点”：
typedef pair<int,int> pii;
vector<int> dijkstra(vector<vector<pii>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 过期条目，跳过
for (auto [v, w] : graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
要点：d > dist[u] 的过期判断不能省，否则重复松弛会拖慢性能。
Bellman-Ford：含负权边
对所有边做 V−1 轮”松弛”（每轮保证至少多确定一条最短路径的边），第 V 轮若还能松弛，说明存在负权环。O(V·E)，能处理负权边并检测负权环。
SPFA 是它的队列优化版（只有被更新过的节点才重新松弛），平均很快但最坏 O(V·E)，在构造数据下会超时——竞赛中很多人更倾向 Bellman-Ford 或直接避开负权场景。
Floyd-Warshall：全源最短路径
动态规划：dist[i][j] 表示 i→j 的最短距离，外层枚举中间点 k，内层枚举所有点对尝试经由 k 中转。三层循环，代码极简：
void floyd(vector<vector<int>>& dist) {
int n = dist.size();
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
O(V³)，适合 V ≤ 300 左右的稠密图全源问题。
选型指南
| 场景 | 推荐 | 理由 |
|---|---|---|
| 非负权、单源 | Dijkstra（堆优化） | 效率高、稳定，默认首选 |
| 含负权边、单源 | Bellman-Ford | 能处理负权并检测负权环 |
| 全源、节点少 | Floyd-Warshall | 代码简单，直接得到所有点对距离 |
| 无权图 | BFS | O(V+E)，比 Dijkstra 更快 |
应用实例：地图导航（Dijkstra）、网络路由（Bellman-Ford 处理代价变化）、游戏 AI 寻路（A* 是 Dijkstra 的启发式变种）、社交网络最短距离（BFS）。