Dijkstra算法实现单源最短路径问题解析

1. 题目背景与需求分析单源最短路径Single-Source Shortest PathSSSP是图论中的经典问题也是算法竞赛中的高频考点。洛谷P3371作为该问题的模板题主要考察对Dijkstra算法或SPFA算法的实现能力。题目给定一个包含n个顶点、m条边的有向图要求计算从源点s到所有其他顶点的最短路径长度。在实际应用中最短路径算法广泛存在于交通导航系统中的路线规划网络路由协议的路径选择物流配送中的最优路径计算游戏AI中的寻路算法注意本题特别标注为弱化版意味着测试数据不包含负权边因此使用Dijkstra算法更为合适。若存在负权边则需要考虑SPFA或Bellman-Ford算法。2. 算法选型与复杂度分析2.1 Dijkstra算法原理Dijkstra算法的核心思想是贪心策略通过维护一个未确定最短路径的顶点集合每次从中选取当前距离源点最近的顶点进行松弛操作。其正确性基于以下关键点非负权边保证局部最优即全局最优每次松弛操作不会使已确定最短路径的顶点距离变小算法伪代码表示def dijkstra(graph, source): dist [INF] * n dist[source] 0 visited set() heap MinHeap() heap.push((0, source)) while heap: current_dist, u heap.pop() if u in visited: continue visited.add(u) for v, weight in graph[u]: if dist[v] current_dist weight: dist[v] current_dist weight heap.push((dist[v], v)) return dist2.2 复杂度对比算法时间复杂度空间复杂度适用场景Dijkstra(堆)O((VE)logV)O(VE)无负权边SPFA平均O(E)最坏O(VE)O(VE)含负权边无负环Bellman-FordO(VE)O(VE)含负权边可检测负环对于本题n≤10^4的数据规模使用堆优化的Dijkstra算法更为稳妥可以保证在时限内完成计算。3. 代码实现细节3.1 数据结构设计采用邻接表存储图结构更节省空间vectorvectorpairint, int graph(n1); // 邻接表graph[u] { (v1,w1), (v2,w2)... }优先队列需要自定义比较函数struct Node { int id, dist; bool operator(const Node other) const { return dist other.dist; } }; priority_queueNode, vectorNode, greaterNode pq;3.2 完整实现代码#include iostream #include vector #include queue #include climits using namespace std; const int INF INT_MAX; void dijkstra(int n, int s, vectorvectorpairint,int graph, vectorint dist) { dist.assign(n1, INF); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,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] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { int n, m, s; cin n m s; vectorvectorpairint,int graph(n1); for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].emplace_back(v, w); } vectorint dist(n1); dijkstra(n, s, graph, dist); for (int i 1; i n; i) { cout (dist[i] INF ? 2147483647 : dist[i]) ; } return 0; }3.3 关键优化点延迟删除技术优先队列中可能存在同一节点的多个副本通过if (d dist[u]) continue跳过过期数据邻接表存储相比邻接矩阵稀疏图下空间复杂度从O(V^2)降至O(VE)STL优先队列使用greaterpairint,int实现最小堆避免手写堆结构4. 常见问题与调试技巧4.1 典型错误案例未初始化距离数组// 错误写法 vectorint dist; // 未初始化大小和初值 // 正确写法 vectorint dist(n1, INF);优先队列比较函数错误// 错误写法 - 比较方向反了 priority_queuepairint,int pq; // 默认最大堆 // 正确写法 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq;整数溢出处理// 错误写法 - 未考虑边权累加溢出 if (dist[v] dist[u] w) // 当dist[u]w超过INT_MAX时溢出 // 正确写法 - 增加溢出判断 if (dist[u] ! INF dist[v] dist[u] w)4.2 测试用例设计设计测试用例时应考虑以下边界情况单顶点图n1链式图所有顶点形成一条链完全图任意两顶点间都有边源点无法到达某些顶点的情况多条平行边同一对顶点间有多条不同权值的边示例测试数据// 情况4顶点4不可达 4 3 1 1 2 5 2 3 3 1 3 9 // 预期输出0 5 8 21474836475. 算法扩展与变种5.1 路径记录如需输出具体路径而不仅是距离可增加pre数组记录前驱节点vectorint pre(n1, -1); // 松弛时更新前驱 if (dist[v] dist[u] w) { dist[v] dist[u] w; pre[v] u; pq.push({dist[v], v}); } // 输出路径 void print_path(int v) { if (v -1) return; print_path(pre[v]); cout v ; }5.2 多源最短路径对于需要计算所有顶点对之间最短路径的场景可采用Floyd-Warshall算法O(V^3)对每个顶点运行DijkstraO(V(EVlogV))5.3 双标准最短路径当需要考虑路径长度和边权之外的其他因素如费用、舒适度时可将优先队列元素扩展为多元组struct State { int id; int dist; int cost; bool operator(const State other) const { return dist other.dist ? cost other.cost : dist other.dist; } };在实际编码竞赛中建议将Dijkstra算法封装为可重用模板。我个人的实现习惯会包含以下特性支持邻接表和邻接矩阵两种存储方式可配置是否记录路径包含防溢出处理使用更高效的配对堆pb_ds库替代STL优先队列对于时间要求特别严格的题目还可以尝试以下优化使用手写堆替代STL优先队列在已知图结构的情况下使用Dial算法当边权为小整数时使用位运算优化比较操作