1. 城市最短路问题概述
城市最短路问题是图论中的经典算法问题，也是信息学奥赛中的高频考点。题目通常给出一个城市道路网络图，要求计算从起点到终点的最短路径。这类问题在实际应用中非常广泛，比如导航软件路线规划、物流配送路径优化等。
在信息学奥赛一本通的P1381题中，给出了一个典型的城市道路网络，要求参赛者使用Dijkstra算法求解最短路。但事实上，这类问题至少有四种主流解法，每种方法都有其适用场景和特点。作为算法竞赛选手，掌握多种解法不仅能提高解题灵活性，还能深入理解不同算法间的内在联系。
2. Dijkstra算法详解
2.1 算法原理与实现
Dijkstra算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出，是解决单源最短路径问题的经典算法。其核心思想是贪心策略：每次从尚未确定最短路径的顶点中，选取当前距离起点最近的顶点，然后更新其邻接顶点的距离。
标准实现步骤如下：
- 初始化：设置起点距离为0，其他顶点距离为无穷大
- 选择当前距离起点最近的未处理顶点u
- 对u的所有邻接顶点v进行松弛操作：
- 如果dist[u] + w(u,v) < dist[v]，则更新dist[v]
- 标记u为已处理
- 重复步骤2-4，直到所有顶点都被处理
// Dijkstra算法C++实现 void dijkstra(int start) { priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<int> dist(n, INF); dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); if (d > dist[u]) continue; for (auto &edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }2.2 算法优化与变种
标准Dijkstra算法使用优先队列实现，时间复杂度为O((V+E)logV)。在实际应用中，我们可以根据具体场景进行优化：
- 堆优化：使用二叉堆或斐波那契堆提高优先级队列效率
- 双向Dijkstra：同时从起点和终点开始搜索，相遇时终止
- A*算法：引入启发式函数，优先探索可能更优的路径
注意：Dijkstra算法不能处理负权边的情况。如果图中存在负权边，需要使用Bellman-Ford或SPFA算法。
3. 其他最短路算法解析
3.1 Floyd-Warshall算法
Floyd算法是一种动态规划算法，用于求解所有顶点对之间的最短路径。其核心思想是通过中间顶点逐步优化路径。
算法特点：
- 时间复杂度O(V³)，适合稠密图
- 可以处理负权边（但不能有负权回路）
- 代码实现简洁
// Floyd算法实现 for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);3.2 Bellman-Ford算法
Bellman-Ford算法可以处理带有负权边的图，并能检测负权回路。其基本思想是通过松弛操作逐步逼近最短路径。
算法特点：
- 时间复杂度O(VE)
- 可以进行V-1轮松弛操作
- 最后一轮检查是否存在负权回路
3.3 SPFA算法
SPFA（Shortest Path Faster Algorithm）是Bellman-Ford算法的队列优化版本，在随机图上通常表现更好。
算法特点：
- 平均时间复杂度O(E)，最坏情况下O(VE)
- 使用队列避免不必要的松弛操作
- 同样可以检测负权回路
4. 算法比较与选择指南
4.1 性能对比
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| Dijkstra | O((V+E)logV) | O(V+E) | 无负权边的单源最短路 |
| Floyd | O(V³) | O(V²) | 所有顶点对的最短路 |
| Bellman-Ford | O(VE) | O(V+E) | 含负权边的单源最短路 |
| SPFA | O(E)~O(VE) | O(V+E) | 含负权边的单源最短路 |
4.2 选择建议
- 单源最短路且无负权边：优先选择Dijkstra
- 需要所有顶点对最短路：考虑Floyd
- 存在负权边：使用Bellman-Ford或SPFA
- 图非常稀疏：SPFA可能表现更好
- 图非常稠密：考虑使用朴素Dijkstra
5. 竞赛实战技巧
5.1 常见陷阱与规避
- 负权边误用Dijkstra：会导致错误结果，需改用Bellman-Ford
- 优先队列实现错误：确保使用最小堆而非最大堆
- 邻接表存储不当：稀疏图应使用邻接表而非邻接矩阵
- 无穷大值设置不当：应足够大但避免溢出
5.2 优化技巧
- 输入输出优化：使用快速IO方法处理大规模数据
- 内存预分配：避免动态内存分配带来的开销
- 算法组合：根据图特性组合使用不同算法
- 提前终止：某些情况下可以提前结束算法执行
5.3 题目变形处理
竞赛中常见的最短路问题变形包括：
- 次短路问题
- k短路问题
- 带有额外约束的最短路
- 动态图的最短路
对于这些变形，通常需要在标准算法基础上进行适当修改。例如，次短路问题可以维护两个距离数组，分别记录最短和次短距离。
6. 代码模板与实例
6.1 Dijkstra完整模板
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1e5+5; vector<pair<int,int>> adj[MAXN]; int dist[MAXN]; void dijkstra(int start) { memset(dist, INF, sizeof(dist)); dist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; int d = pq.top().first; pq.pop(); if (d > dist[u]) continue; for (auto &edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } } int main() { int n, m, start; cin >> n >> m >> start; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); // 如果是无向图，还需要添加反向边 // adj[v].push_back({u, w}); } dijkstra(start); for (int i = 1; i <= n; i++) { if (dist[i] == INF) cout << "INF "; else cout << dist[i] << " "; } return 0; }6.2 信息学奥赛一本通P1381题解
题目描述：给定n个城市和m条道路，每条道路有长度，求从城市s到城市t的最短路径。
解法分析：本题是标准的单源最短路问题，没有负权边，适合使用Dijkstra算法。以下是AC代码的核心部分：
void solve() { int n, m, s, t; cin >> n >> m >> s >> t; vector<vector<pair<int,int>>> adj(n+1); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); // 无向图 } vector<int> dist(n+1, INF); dist[s] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } cout << dist[t] << endl; }在实际竞赛中，除了正确实现算法外，还需要注意以下几点：
- 使用足够大的INF值但避免溢出
- 无向图要添加双向边
- 使用更快的输入方式处理大规模数据
- 优先队列的排序方向要正确
7. 算法扩展与应用
7.1 次短路求解
次短路问题可以通过修改Dijkstra算法来解决。基本思路是维护两个距离数组：dist0记录最短路，dist1记录次短路。在松弛操作时，考虑三种情况：
- 新路径比最短路更短
- 新路径介于最短路和次短路之间
- 新路径等于最短路（需要特殊处理）
7.2 带有边数限制的最短路
某些问题可能限制路径的边数不超过k。这类问题可以使用动态规划结合Bellman-Ford的思想解决。定义dp[k][v]表示最多经过k条边到达v的最短距离，然后进行k轮松弛操作。
7.3 实际应用案例
- 导航系统：Dijkstra及其变种广泛应用于地图导航
- 网络路由：OSPF等路由协议基于最短路算法
- 交通规划：优化公共交通线路
- 游戏AI：寻路算法的基础
在解决实际问题时，往往需要根据具体约束对标准算法进行调整。例如，在导航系统中，除了路径长度外，还需要考虑实时交通状况、转弯惩罚等因素。
