Dijkstra算法详解：从原理到实现，解决最短路径问题

发布时间：2026/7/29 5:58:47
Dijkstra算法详解：从原理到实现，解决最短路径问题
1. 从“最短路径”说起一个看似简单却无处不在的问题“最短路径”这四个字听起来简单直白但它几乎是所有与“连接”和“移动”相关的计算问题的核心。从我们每天使用的手机地图导航到物流公司规划全国配送路线再到网络路由器决定数据包的下一跳甚至是在游戏里让角色自动寻路避开障碍物背后都离不开最短路径算法的身影。信息学奥赛OI的经典教材《信息学奥赛一本通》中将“最短路径问题”作为图论部分的核心例题其重要性不言而喻。这道编号为1342的例题正是初学者叩开图论与算法优化大门的一块关键敲门砖。很多刚接触图论的同学一看到“最短路径”可能立刻会想到“两点之间线段最短”的几何公理。但在计算机的世界里尤其是在由点和边构成的“图”中情况要复杂得多。这里的“短”不再是纯粹的物理距离它可以是时间、成本、权重等任何可量化的代价。问题的核心在于在一个由顶点V和带权边E构成的图中给定一个起点和一个终点如何找到一条从起点到终点的路径使得这条路径上所有边的权重之和最小这就是最短路径问题的本质。这道例题之所以经典是因为它剥离了复杂场景的外衣将一个抽象的、模型化的最短路径问题直接呈现在我们面前。它不涉及动态障碍、实时交通信息也不考虑多目标优化就是最基础的、静态的、有权图的最短路径求解。掌握这个基础模型就像学会了加减乘除是后续解决所有复杂变种问题如次短路径、第K短路径、带有负权边的最短路径等的基石。接下来我将结合常见的竞赛场景和实战经验带你一步步拆解这个问题不仅弄懂“怎么做”更要明白“为什么这么做”以及在实际编码和调试中会遇到哪些“坑”。2. 问题建模将现实抽象为图在动手写任何代码之前我们必须先完成最关键的一步将问题描述抽象成计算机能够处理的图模型。这是算法竞赛和实际工程中至关重要的一环模型建错了后面再精巧的算法也是徒劳。题目通常会给出一些顶点城市、路口、网络节点等和连接这些顶点的边道路、线路、连接等每条边会有一个权值距离、时间、费用等。我们的输入格式一般如下首先读入顶点数n和边数m然后依次读入m条边每条边包含三个信息起点u、终点v和权重w。最后读入查询的起点s和终点t。例如一个简单的输入可能是5 7 1 2 5 1 3 2 2 3 1 2 4 3 3 4 6 3 5 4 4 5 2 1 5这表示一个有5个顶点、7条边的图。我们需要计算从顶点1到顶点5的最短路径长度。这里有几个关键的建模细节和常见陷阱图的类型判断首先需要判断这是有向图还是无向图。例题通常是无向图意味着边(u, v, w)表示可以从u走到v也可以从v走到u代价都是w。在代码存储时我们需要存储两条有向边u-v权重w和v-u权重w。如果题目明确是有向图则只存一条边。这是一个非常容易疏忽的点一旦存错结果必然错误。权重的范围与类型权重w的数据类型是什么是整数还是浮点数范围有多大这决定了我们在代码中应该使用int还是long long甚至是double。例如如果权重是距离且可能为小数如两点间欧氏距离就必须用double。同时权重的范围也影响了我们在初始化“最短距离数组”时“无穷大”INF值的设定。INF必须是一个比任何可能的最短路径总和都大的数但又不能太大导致加法溢出。对于int类型通常设INF 0x3f3f3f3f这个值大约10^9满足大多数情况且两个INF相加不会溢出成负数。顶点的编号顶点通常从1开始编号而我们的数组习惯从0开始索引。在存储邻接表或邻接矩阵时需要保持一致要么全部转换为0-based索引要么在读取和访问时进行-1操作。我个人的习惯是在读取输入后立即将顶点编号减1转换为0-based索引这样可以直接用作数组下标不易出错。在输出时如果需要还原为1-based编号再加1即可。重边和自环图中可能存在多条连接同一对顶点的边重边也可能存在起点和终点相同的边自环。对于最短路径问题重边我们通常只保留权重最小的那条因为走权重大的边显然不是最优解。自环则可以直接忽略因为走自环不会改变当前位置只会增加路径长度。在邻接矩阵中存储时可以用min操作来处理重边在邻接表中虽然可以都存下来但在使用某些算法如朴素Dijkstra时这会导致不必要的性能损耗。完成建模后我们就得到了一个清晰的数据结构邻接矩阵或邻接表来存储这个图接下来就可以选择算法来求解了。3. 算法选型为什么是Dijkstra面对最短路径问题我们有几个候选算法Floyd-Warshall多源最短路、Bellman-Ford带负权边、SPFABellman-Ford的队列优化、以及Dijkstra算法。对于例题这种边权为非负数的单源最短路径问题Dijkstra算法是公认的最优选择。为什么是Dijkstra我们来对比一下Floyd-Warshall计算图中所有顶点对之间的最短路径时间复杂度为 O(n^3)。当只需要一个起点到其他点的距离时用它就是“杀鸡用牛刀”效率太低。Bellman-Ford/SPFA能处理带有负权边的图并检测负权环。但它们的平均时间复杂度高于DijkstraSPFA最坏情况也是O(VE)。既然题目保证了边权非负我们当然要选用在非负权图上效率更高的Dijkstra。Dijkstra算法基于贪心策略在非负权图上能保证找到最短路径。其核心思想是将顶点分为两个集合已确定最短距离的集合S和未确定的集合T。每次从T中选出当前距离起点最近的顶点u将其加入S并用u来松弛更新其所有邻居顶点的距离。一旦终点被加入S算法就可以提前结束。Dijkstra算法有两种主流实现方式适用于不同规模的数据1. 朴素版本邻接矩阵存储适合稠密图边数 m 接近 n^2且顶点数 n 较小通常 n 500。它的时间复杂度是 O(n^2)。实现非常简单用一个dist[]数组记录起点到各点的当前最短距离用一个visited[]数组标记顶点是否已加入集合S。每次循环遍历所有顶点找出未访问且dist最小的顶点u然后遍历所有顶点用graph[u][v]来更新dist[v]。这种方法的代码直观易于理解和调试是初学者必须掌握的实现。2. 堆优化版本邻接表存储适合稀疏图边数 m 远小于 n^2或顶点数 n 较大n 1000的情况。时间复杂度为 O((mn) log n)。它使用一个最小堆优先队列来高效地获取当前距离最小的顶点。我们不再需要visited数组因为同一个顶点可能被多次加入堆但我们只处理第一次从堆中取出的版本此时的距离才是最短的。这是竞赛和工程中的标配实现。对于《一本通》的例题通常数据规模不会特别大两种实现都可能适用。但作为学习和练习我强烈建议两种都亲手实现一遍。理解朴素版本能让你透彻掌握Dijkstra的贪心本质而掌握堆优化版本则是你解决更大规模问题的必备技能。注意Dijkstra算法不能处理带有负权边的图因为其贪心策略基于一个假设“当前未访问顶点中距离最小的顶点其距离不会再被更新”。如果存在负权边这个假设就不成立了因为通过后续的负权边可能产生一条更短的路径。这是Dijkstra算法的根本局限性务必牢记。4. 实战编码从朴素实现到堆优化理论清晰了我们开始动手写代码。我会给出两种实现的详细代码、注释并对比它们的特点。4.1 朴素Dijkstra实现详解假设我们使用邻接矩阵g[N][N]存储图dist[i]存储起点s到顶点i的最短距离vis[i]标记顶点i是否已确定最短距离。#include iostream #include cstring #include algorithm using namespace std; const int N 1005; // 根据题目最大顶点数设定 const int INF 0x3f3f3f3f; // 表示“无穷大” int n, m, s, t; int g[N][N]; // 邻接矩阵 int dist[N]; // 最短距离数组 bool vis[N]; // 访问标记数组 void dijkstra(int start) { // 1. 初始化 memset(dist, 0x3f, sizeof(dist)); // 所有距离初始化为无穷大 memset(vis, false, sizeof(vis)); // 所有顶点未访问 dist[start] 0; // 起点到自己的距离为0 // 2. 循环n次每次确定一个顶点的最短距离 for (int i 0; i n; i) { // 2.1 寻找当前未访问顶点中dist最小的顶点u int u -1; for (int j 0; j n; j) { if (!vis[j] (u -1 || dist[j] dist[u])) { u j; } } // 如果找不到说明剩下的顶点不可达可以提前结束 if (u -1 || dist[u] INF) break; // 2.2 标记顶点u已访问已确定最短路径 vis[u] true; // 2.3 用顶点u松弛其所有邻居顶点v for (int v 0; v n; v) { // 如果u和v之间有边且通过u到v比当前已知的到v的距离更短 if (g[u][v] ! INF dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; } } } } int main() { cin n m; // 初始化邻接矩阵 memset(g, 0x3f, sizeof(g)); for (int i 0; i n; i) g[i][i] 0; // 自己到自己的距离为0非必需 for (int i 0; i m; i) { int u, v, w; cin u v w; u--; v--; // 转换为0-based索引 // 无向图存两条边。如果有重边取最小值。 g[u][v] min(g[u][v], w); g[v][u] min(g[v][u], w); } cin s t; s--; t--; // 转换索引 dijkstra(s); if (dist[t] INF) { cout -1 endl; // 根据题目要求不可达输出-1或其他 } else { cout dist[t] endl; } return 0; }代码要点与避坑指南INF的选择0x3f3f3f3f是一个很好的选择因为它足够大~1e9且memset可以方便地用0x3f字节来填充使得每个int都是这个值。两个INF相加也不会溢出成负数0x3f3f3f3f * 2 0x7fffffff。重边处理在读入边时使用g[u][v] min(g[u][v], w);可以自动处理重边只保留最短的边。提前跳出在寻找u的循环后如果u -1或dist[u] INF说明剩余顶点都与起点不连通可以提前结束算法这是一个小的优化。索引转换在main函数中统一进行u--, v--操作将1-based输入转换为0-based存储能极大减少后续代码的思维负担和出错概率。4.2 堆优化Dijkstra实现详解当图是稀疏图时朴素方法O(n^2)的复杂度就不可接受了。我们需要使用邻接表存储并用优先队列最小堆来优化寻找dist最小顶点的过程。#include iostream #include cstring #include algorithm #include vector #include queue using namespace std; typedef pairint, int PII; // first: 距离, second: 顶点编号 const int N 100005; // 顶点数上限 const int M 200005; // 边数上限无向图要存两倍 const int INF 0x3f3f3f3f; int n, m, s, t; int h[N], e[M], ne[M], w[M], idx; // 邻接表 int dist[N]; bool vis[N]; // 这里vis数组仍然有用用于判断是否已确定最短距离 void add(int a, int b, int c) { e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx; } void dijkstra(int start) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[start] 0; priority_queuePII, vectorPII, greaterPII pq; // 最小堆 pq.push({0, start}); // 放入起点距离为0 while (!pq.empty()) { // 3.1 取出当前距离最小的顶点 auto t pq.top(); pq.pop(); int u t.second; int d t.first; // 关键如果这个顶点已经处理过距离已确定则跳过 if (vis[u]) continue; // 标记为已处理 vis[u] true; // 3.2 松弛操作遍历u的所有出边 for (int i h[u]; i ! -1; i ne[i]) { int v e[i]; int new_dist d w[i]; if (new_dist dist[v]) { dist[v] new_dist; // 将新的距离和顶点放入堆中。注意同一个v可能被多次放入堆。 pq.push({dist[v], v}); } } } } int main() { cin n m; // 初始化邻接表头指针 memset(h, -1, sizeof(h)); idx 0; for (int i 0; i m; i) { int u, v, w_val; cin u v w_val; u--; v--; add(u, v, w_val); add(v, u, w_val); // 无向图 } cin s t; s--; t--; dijkstra(s); if (dist[t] INF) { cout -1 endl; } else { cout dist[t] endl; } return 0; }堆优化版本的核心与陷阱vis数组的必要性很多人认为堆优化版本不需要vis数组这是错误的。因为同一个顶点v可能被多次加入堆每次松弛更新距离时都会加入。当我们从堆中取出一个顶点时如果它的距离d大于当前dist[u]说明这个记录是过时的应该直接跳过。vis数组的作用就是标记该顶点是否已被确定最短距离即第一次从堆中取出时。一旦确定后续所有从堆中取出的该顶点记录都可以跳过。用if (d dist[u]) continue;也可以替代vis数组逻辑等价。优先队列的定义priority_queuePII, vectorPII, greaterPII定义了一个最小堆pair默认按first排序所以我们把距离放在first顶点编号放在second。复杂度分析每个顶点最多被加入堆一次确定最短距离后每条边最多引发一次松弛操作和一次入堆操作。堆操作是O(log n)所以总复杂度是O((mn) log n)。对于稀疏图这比O(n^2)快得多。邻接表存储注意无向图边的数量m要乘以2来分配数组大小M。h数组初始化为-1很重要。5. 路径还原如何记录并输出具体走法很多时候题目不仅要求输出最短路径的长度还要求输出具体的路径序列。这就需要我们在算法运行过程中记录下“最短路径树”上每个顶点的前驱节点。原理在松弛操作dist[v] dist[u] w成功执行时意味着我们找到了一条从起点到v的更短路径而这条路径是通过u过来的。因此我们可以记录pre[v] u。我们在两种版本的Dijkstra中都可以加入一个pre数组初始化为-1来实现。以堆优化版本为例添加路径还原int pre[N]; // 前驱节点数组 void dijkstra(int start) { // ... 初始化部分同上 ... memset(pre, -1, sizeof(pre)); // 初始化前驱 // ... while (!pq.empty()) { // ... 取出顶点u ... if (vis[u]) continue; vis[u] true; for (int i h[u]; i ! -1; i ne[i]) { int v e[i]; int new_dist d w[i]; if (new_dist dist[v]) { dist[v] new_dist; pre[v] u; // 关键记录v的前驱是u pq.push({dist[v], v}); } } } } // 输出从起点s到终点t的路径逆序 void print_path(int t) { if (t -1) return; print_path(pre[t]); // 递归先打印前驱 cout t 1 ; // 输出时转换回1-based编号 } // 在main函数中调用 if (dist[t] ! INF) { cout dist[t] endl; print_path(t); // 输出路径 } else { cout -1 endl; }注意事项这样打印出来的路径是从起点到终点的顺序。因为我们是递归到起点再开始打印。如果需要存储路径以便后续使用可以将其压入一个vector中。如果存在多条最短路径标准的Dijkstra算法只会记录其中一条取决于松弛操作的顺序。如果需要所有最短路径则需要更复杂的数据结构如vectorint pre[N]来存储所有可能的前驱并使用DFS进行回溯。6. 边界条件与常见错误排查即使算法原理和代码都懂了在实际提交时仍然可能遇到各种“Wrong Answer”。下面是一些高频的坑点和排查思路1. 无穷大 INF 设置不当问题INF设置太小导致本应不可达的点被错误地松弛。检查估算最大可能路径长度。如果有n个顶点最大边权为W那么最长路径最多包含n-1条边总长不超过(n-1)*W。INF必须大于这个值。使用0x3f3f3f3f约1e9对于大多数题目n*W 1e9是安全的。2. 图存储错误有向/无向混淆症状样例能过但提交后部分测试点错误。排查这是最常见错误之一。反复审题确认图是有向还是无向。如果是无向图代码中是否存了双向边我习惯在注释里明确写上// 无向图或// 有向图以提醒自己。3. 重边未处理症状同样样例能过但可能在某些包含重边的测试点上出错。排查对于邻接矩阵使用g[u][v] min(g[u][v], w);。对于邻接表虽然可以存储所有重边但在使用朴素Dijkstra时这会导致不必要的松弛判断虽然结果正确但可能超时。保险起见可以在读入时用邻接矩阵或map暂存最小边权最后再构建邻接表。4. 顶点编号转换错误症状随机出现数组越界、结果错误。排查坚持一个原则内部存储统一使用0-based索引。在main函数读入u, v后立即进行u--; v--;。在输出路径时再统一1转换回来。这样可以避免在算法核心逻辑中混杂索引转换降低出错率。5. 堆优化Dijkstra中 vis 数组或距离判断遗漏症状程序可能陷入死循环或者结果错误通常偏大。排查务必记得在从堆中取出顶点后判断if (vis[u]) continue;或if (d dist[u]) continue;。这是堆优化版本正确性的关键保障。6. 数据类型溢出症状输入较大时结果出现负数或明显错误。排查检查所有与距离、权重相关的变量类型。如果n*w可能超过int范围约2e9果断使用long long。dist数组、INF常量、中间计算结果都要换。调试技巧对于复杂样例可以尝试输出中间结果。例如在Dijkstra循环中打印每次选中的顶点u和更新后的dist数组。与手动模拟的结果对比能快速定位逻辑错误。7. 性能优化与进阶思考掌握了基础版本后我们可以思考一些优化和进阶方向这在解决更复杂问题时很有用。1. 稀疏图与稠密图的自动选型 在竞赛中有时你无法预判数据是稠密还是稀疏。一个简单的策略是如果m的数量级接近n^2使用朴素DijkstraO(n^2)否则使用堆优化DijkstraO(m log n)。可以写一个判断或者直接准备两个版本的函数。2. 使用更快的堆 C STL的priority_queue通常足够快。但在极端性能要求的场景下手写二叉堆、斐波那契堆或使用std::set可以修改元素可能略有优势但对于OI/ACM竞赛priority_queue是完全够用的。3. 多源最短路径与单源最短路径 如果问题需要计算多个起点到多个终点的最短路径不要对每个起点都跑一遍DijkstraO(k * (m log n))。考虑 * 如果图是静态的且查询次数k很多可以使用Floyd-Warshall算法O(n^3)预处理所有点对距离之后每次查询就是O(1)。 * 如果图是静态的但只有少数几个源点可以对每个源点跑一次Dijkstra结果存下来。 * 如果图是动态的边权会变则需要更复杂的数据结构。4. 输出路径的优化 递归输出路径在路径很长时可能有栈溢出风险尽管OI中通常不会。可以用循环迭代的方式先将路径节点存入数组再逆序输出。vectorint path; for (int v t; v ! -1; v pre[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int node : path) cout node 1 ;5. 理解算法的本质与变种 Dijkstra算法本质是BFS广度优先搜索的加权版本。普通BFS的队列保证了“层序”遍历而Dijkstra的优先队列保证了“按当前最短距离”的顺序遍历。理解这一点有助于你将其思想应用到其他类似问题例如使用“双端队列BFS0-1 BFS”处理边权仅为0或1的图其时间复杂度可以降到O(VE)。最短路径问题是一个深不见底的领域从经典的Dijkstra、Bellman-Ford、Floyd到应对特殊图结构的算法如DAG上的拓扑排序求最短路再到用于寻路的A*算法以及实际网络中的路由协议如OSPF。这道《一本通》的例题为我们打开了这扇大门。我个人的体会是基础算法的实现一定要做到“肌肉记忆”般熟练同时要深刻理解其背后的图模型和贪心/动态规划思想。这样当遇到变形题时你才能快速识别出问题的本质并选择或修改合适的算法来解决它。在平时练习时不妨多找一些需要输出路径、处理重边、判断连通性、甚至边权有少量负值需要结合SPFA判断的变种题来做巩固和拓展对这个知识点的掌握。