Dijkstra算法实战：PTA紧急救援问题解析与优化
1. 项目概述：PTA L2-001紧急救援问题解析
这道PTA题目是典型的带权图最短路径应用场景，要求使用Dijkstra算法解决城市紧急救援问题。题目会给出城市间的道路信息（边权）和每个城市的救援队伍数量（点权），需要找出从起点到终点的最短路径，并在多条最短路径中选择救援队伍最多的那条。
在实际工程中，这类算法广泛应用于导航系统、物流配送、网络路由等场景。比如救护车选择最优路线时，既要考虑路程最短，也要考虑能调配最多医疗资源的路径。
2. 核心算法解析：Dijkstra的实现要点
2.1 基础Dijkstra框架
标准Dijkstra算法使用优先队列（最小堆）实现，时间复杂度O(ElogV)。核心数据结构包括：
dist[]数组记录起点到各点的最短距离visited[]数组标记已确定最短路径的点- 优先队列存储待处理的节点
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, start}); dist[start] = 0; while(!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if(visited[u]) continue; visited[u] = true; for(auto &[v, w] : graph[u]) { if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } }2.2 题目特殊要求的扩展
本题需要在标准Dijkstra基础上增加三个维度的信息：
num[]记录到每个点的最短路径数量teams[]记录到每个点的最大救援队数量pre[]记录路径前驱节点用于最后输出路径
关键更新逻辑：
if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; num[v] = num[u]; teams[v] = teams[u] + rescue[v]; pre[v] = u; pq.push({dist[v], v}); } else if(dist[v] == dist[u] + w) { num[v] += num[u]; if(teams[u] + rescue[v] > teams[v]) { teams[v] = teams[u] + rescue[v]; pre[v] = u; } }3. 完整代码实现与逐行解析
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; void dijkstra(int n, int s, int d, vector<vector<pair<int,int>>>& graph, vector<int>& rescue, vector<int>& path) { vector<int> dist(n, INF); vector<int> num(n, 0); vector<int> teams(n, 0); vector<int> pre(n, -1); vector<bool> visited(n, false); dist[s] = 0; num[s] = 1; teams[s] = rescue[s]; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, s}); while(!pq.empty()) { auto [dis, u] = pq.top(); pq.pop(); if(visited[u]) continue; visited[u] = true; for(auto &[v, w] : graph[u]) { if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; num[v] = num[u]; teams[v] = teams[u] + rescue[v]; pre[v] = u; pq.push({dist[v], v}); } else if(dist[v] == dist[u] + w) { num[v] += num[u]; if(teams[u] + rescue[v] > teams[v]) { teams[v] = teams[u] + rescue[v]; pre[v] = u; } } } } // 回溯路径 int cur = d; while(cur != -1) { path.push_back(cur); cur = pre[cur]; } reverse(path.begin(), path.end()); cout << num[d] << " " << teams[d] << endl; for(int i = 0; i < path.size(); ++i) { if(i != 0) cout << " "; cout << path[i]; } } int main() { int N, M, S, D; cin >> N >> M >> S >> D; vector<int> rescue(N); for(int i = 0; i < N; ++i) { cin >> rescue[i]; } vector<vector<pair<int,int>>> graph(N); for(int i = 0; i < M; ++i) { int u, v, w; cin >> u >> v >> w; graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); } vector<int> path; dijkstra(N, S, D, graph, rescue, path); return 0; }4. 关键难点与调试技巧
4.1 边界条件处理
- 起点和终点相同的情况：需要特殊处理，此时路径数为1，救援队数量就是该城市的数量
- 不可达情况：题目保证有解，实际工程中需要增加判断
- 城市编号从0开始：注意题目输入要求，避免off-by-one错误
4.2 常见错误排查
优先队列使用错误：
- 错误做法：直接修改队列中的元素
- 正确做法：将新状态重新push进队列，通过visited数组过滤旧状态
路径计数错误：
// 错误写法 num[v] = 1; // 正确写法 num[v] += num[u];救援队累加错误：
// 错误写法（漏加当前城市救援队） teams[v] = teams[u]; // 正确写法 teams[v] = teams[u] + rescue[v];
4.3 性能优化建议
- 使用邻接表而非邻接矩阵存储稀疏图
- 优先队列使用pair时，将距离放在first元素（默认按first排序）
- 在找到终点后可提前终止算法（题目不要求时可以优化）
5. 算法扩展与变种思考
5.1 堆优化与斐波那契堆
当图规模极大时（如V>1e5），可以使用更高效的斐波那契堆实现，将时间复杂度降至O(E+VlogV)。不过C++标准库未提供，需要手动实现或使用第三方库。
5.2 A*算法的适用性
如果问题中能设计合理的启发式函数（如地理坐标间的直线距离），A*算法通常比Dijkstra更快找到终点。但在本题中由于缺少位置信息，Dijkstra是最佳选择。
5.3 动态图处理
实际场景中道路状况可能实时变化，可以考虑以下优化：
- 增量式Dijkstra：只重新计算受影响的部分路径
- 预处理技术：如Contraction Hierarchies等
6. 实际工程中的应用建议
- 内存优化：对于超大图，可以使用CSR（Compressed Sparse Row）格式存储邻接表
- 并行计算：使用多线程同时处理不同节点的松弛操作
- 持久化存储：预处理好的图结构可以序列化到磁盘，避免每次重新计算
在真实导航系统中，Dijkstra的变种算法通常需要处理：
- 实时交通数据更新
- 多维度权重（距离、时间、收费等）
- 用户偏好设置（避开高速、优先步行等）
调试提示：在VS Code中调试时，可以使用以下launch.json配置观察变量：
{ "version": "0.2.0", "configurations": [ { "name": "C++ Debug", "type": "cppdbg", "request": "launch", "program": "${fileDirname}/${fileBasenameNoExtension}", "args": ["<", "input.txt"], "stopAtEntry": false, "externalConsole": false, "MIMode": "gdb", "setupCommands": [ { "description": "Enable pretty-printing", "text": "-enable-pretty-printing", "ignoreFailures": true } ] } ] }
最后分享一个实用技巧：在竞赛中遇到类似题目时，可以先将标准Dijkstra模板写出来，再根据题目要求逐步添加额外维度的信息处理，这样比一次性写完整代码更不容易出错。