1. 这个算法到底在解决什么问题1.1 从BFS说起为什么最短路不能只靠“层数”大约两年前我在做一个物流派单系统的模拟项目核心需求是给定一张城市道路网车辆从配送站出发要找到前往每个客户点耗时最短的路径。最开始我图省事直接用BFS跑了一遍以为“层数越少就是越快”。测试时数据量小没发现问题后来把真实的道路数据灌进去立刻露出了破绽——BFS假设每条边代价相同每条路走一步的耗时都一样这在无权图里成立可在带权图里完全行不通。举一个最简单的例子A到B有一条直达路车程10分钟A到C有一条小路车程1分钟C到B也有一条路车程1分钟。BFS会认为A→B是最近路径因为只需要“一层”但真实最短路径是A→C→B耗时2分钟。这就是带权图最短路径问题的核心也是Dijkstra算法登场的地方。Dijkstra算法解决的是“单源最短路径”问题在一个所有边权重为非负数的带权有向图或无向图中给定一个起点源点计算它到其余所有顶点的最短路径长度并且在需要时能把整条路径还原出来。这里的“最短”不再由经过的边数决定而是由累计的权重决定。这个算法的应用面极其广凡是你能在生活里想到的“从某个点出发找到代价最小的路线”问题几乎都有它的影子地图导航中的驾车路径规划计算机网络中计算数据包转发的路由表供应链系统里计算仓库到门店的最低运输成本甚至游戏里的AI寻路配合启发式算法可以做进一步优化。适合读这篇文章的人我默认你是刚开始接触最短路径算法的学生、准备面试的开发者或者在项目里突然遇到“带权重的最短路需求”但不知道从何下手的工程师。我会从原理开始一直写到生产级别代码里那些容易踩进去的坑。1.2 先约定好处理的是什么样的图在动笔写代码之前必须把问题边界说清楚否则后面代码和结论都会含糊。Dijkstra算法处理的图满足以下几个条件图可以是有向的也可以是无向的。无向图可以理解为每条边都有双向两条有向边。每条边带有一个非负权重cost。这个权重可以是距离、时间、金钱成本等任意可加和的指标。图中可能存在环。Dijkstra能正确应对环因为它通过“已知最短距离的集合”去扩散不会陷入死循环。权重必须为非负。这是Dijkstra算法的硬性前提。如果存在负权边贪心的假设会被破坏——后文我会详细解释为什么。很多初学者会把Dijkstra和“暴力广搜”混淆只记得它“一层一层往外扩散”却不知道每一层到底扩散的是什么。当你真正理解了它维护的数据结构就会明白它扩散的不是“步数”而是“当前已知的最短距离”。这个差别决定了整个算法的走向。2. 核心原理为什么贪心在这里成立2.1 贪心策略的两种视角我第一次看到Dijkstra算法的描述时几乎所有人都用同一句话概括每次从未确定的节点中选一个当前距离源点最近的点把它加入“已确定”集合然后用它去松弛邻居。这句话背下来很容易但真正支撑它高效工作的是两条隐藏的推论推论一当一个节点被选中并加入已确定集合时它此刻的距离值就是最终的最短距离。为什么敢这么断定因为所有未确定节点的距离值都是“当前已知的最优估计”而选中这个节点意味着它是所有候选者里最小的。假如存在另一条更短的路径到达它那么这条路径一定从某个已确定节点出发经过一个未确定节点再到达当前节点而那个未确定节点在候选者里的距离值一定小于等于这条“假想更短路径”经过它的累计值。既然当前节点已经是候选里最小的了就不可能被一条需要经过更大候选值的路径超越。用大白话说你已经站在所有可能路口的最前面了没人能抄小路抢在你前面到达。推论二每个节点只会被确定一次之后不会因为后续发现更小值而修改。这个推论是推论一的必然结果也是我们能把复杂度压到O((VE) log V)的关键。如果每确定一个节点后还可能回头改前面的结果算法就退化成了一锅乱炖。基于这两条推论算法维护的核心数据结构就浮现出来了——一个按距离值排序的优先队列最小堆每次弹出最小的那个候选节点。2.2 用水管系统理解一遍执行过程我自己的理解方式是把它想象成一个供水系统源点是一个蓄水池每条边是一根管子管子的粗细权重决定了水通过的阻力。Dijkstra算法就是“水最先到达哪里哪个节点就被确定”。因为水总是沿着总阻力最小的路径先到所以一旦某个节点被水浸湿从优先队列中弹出说明那条路径就是全局最优的。这个过程可以分几步看我手画一个例子假设有一个图源点0到节点1的边权为4源点0到节点2的边权为2节点2到节点1的边权为1节点1到节点3的边权为5节点2到节点3的边权为8节点3到节点4的边权为3。执行过程大概是初始化dist[0]0其余为无穷大优先队列放入(0, 0)。弹出(0, 0)确定源点。松弛节点1、2更新dist[1]4, dist[2]2。弹出(2, 2)确定节点2。松弛节点1dist[1]min(4, 21)3更新松弛节点3dist[3]min(∞, 28)10。弹出(3, 1)确定节点1。松弛节点3dist[3]min(10, 35)8。弹出(8, 3)确定节点3。松弛节点4dist[4]8311。弹出(11, 4)确定节点4全部完成。最后得到的最短距离是{0:0, 1:3, 2:2, 3:8, 4:11}。注意在第3步节点1在第一次被更新到4之后并没有被弹出而是在节点2被确定之后又把它松弛到3这正好体现了“未确定节点的距离值只代表当前最优估计不是最终值”这一特点。优先队列里会出现两个(4, 1)和(3, 1)那么陈旧条目会在第4步被跳过——这是我在后面代码里要特别处理的地方。3. 从原理到代码三种通行实现的完整拆解3.1 朴素实现什么时候还值得用Dijkstra的朴素实现长这样每次在所有未确定节点里循环找距离最小的那一个复杂度O(V²)。代码非常简单适合教学和点数很少的稠密图。我写过一版void dijkstra_naive(int src, vectorvectorint g) { int n g.size(); vectorint dist(n, INF); vectorbool visited(n, false); dist[src] 0; for (int i 0; i n; i) { int u -1; int best INF; for (int v 0; v n; v) { if (!visited[v] dist[v] best) { best dist[v]; u v; } } if (u -1) break; visited[u] true; for (int v 0; v n; v) { if (!visited[v] g[u][v] ! INF) { dist[v] min(dist[v], dist[u] g[u][v]); } } } }用邻接矩阵存图g[u][v]直接表示u到v的边权。当图是稠密图接近V²条边时这种写法没有额外堆开销实际跑起来甚至比堆优化版本更快因为堆操作有常数因子。在竞赛题目里看到n 1000的稠密图老老实实用O(V²)反而是最优解。但一旦图的点数到几万级别稀疏图边数约为顶点数的几倍就非常常见这时每轮线性扫描O(V)去找最小点就成了性能瓶颈必须引入优先队列。3.2 堆优化Dijkstra面试和工程中最常用的写法这是我现在项目里最常写的版本也是我推荐绝大多数人掌握的模板。完整代码如下我加了比较详细的注释#include bits/stdc.h using namespace std; const long long INF 1e18; // 别用 INT_MAX后面会讲为什么 void dijkstra(int src, const vectorvectorpairint, long long adj, vectorlong long dist) { int n adj.size(); dist.assign(n, INF); dist[src] 0; // 优先队列pair 的 first 是距离second 是节点编号 // 这里用小顶堆所以要用 greaterpair... priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.emplace(0, src); 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.emplace(dist[v], v); // 只在新距离变小的时候才入队 } } } }这段代码里最关键的一行就是if (d ! dist[u]) continue;。没有这一行算法逻辑上也可能对但会平白多出无数新条目复杂度会退化在图中出现大量重复松弛时甚至可能超时。有了它我们保证每个节点只有一次真正被处理的机会。这就是网友口中“教科书版Dijkstra”和“工程可用版Dijkstra”之间最大的差异。前者常常只写了个伪代码骨架让你意会后者才真正考虑优先队列里陈旧条目的清理。3.3 复杂度分析与选型决策三种常见实现的实际定位如下表格所示实现方式时间复杂度适合场景邻接矩阵朴素版O(V²)稠密图n 2000甚至更小教学演示二叉堆优化版priority_queueO((EV) log V)稀疏图n达到十万、百万级日常工程最常用斐波那契堆优化版O(E V log V)理论上界更优但常数巨大工程中很少手写我个人的选型经验是如果顶点数在1e5左右、边数不超过5e5直接用堆优化版本如果顶点数很小且边特别密朴素版更简单也更可靠。优先队列的常数在C里其实不小但胜在实现简单且不易出错。Python工程师可以参考heapqJava工程师可以用PriorityQueue存int[]思路完全相同。4. 路径还原光有距离算完了等于白干4.1 pre数组的插入时机很多教程讲完距离计算就戛然而止但真实项目里如果不能把“最短路径”本身还原出来距离排序这些成果在业务层面几乎拿不出手。还原路径的核心思路是松弛操作发生时记下“我从谁那里来的”。为此需要在dist数组之外再加一个pre数组专门记录dist[v]是被哪个节点u更新出来的。初始时pre[src] -1表示源点没有前驱每当dist[u] w dist[v]成立就执行pre[v] u。最后从目标节点出发沿着pre一路回退到源点再反转顺序就是完整路径。代码改动非常小核心是在第3.2节的if松弛分支里加一行if (dist[u] w dist[v]) { dist[v] dist[u] w; pre[v] u; pq.emplace(dist[v], v); }打印路径的函数我一般这样写void print_path(int src, int target, const vectorint pre) { if (target src) { cout src - ; return; } print_path(src, pre[target], pre); cout target - ; }这里用递归从终点回溯输出0 - 2 - 1 - 3这种形式。如果目标节点不可达pre[target]会是初始值-1要提前判一下不然递归会越界。4.2 多条最短路径怎么办真实业务里有一个常见小难题最短距离相同但路径可能有很多条。比如外卖平台既想给客户最快送达又希望骑手少等红绿灯这时两条耗时一样的路你会选哪条处理方式取决于业务规则。常见做法是给每条边增加次要属性如红绿灯次数、道路等级在dist[u] w相等时比较次要属性的累计值再决定是否更新pre。还有一种是题目中常见的“求最短路径的条数”那就要维护count数组在发现相等时累加。我试过最省事的方案当最短距离只有个位数条并列路径时直接全部枚举出来再做业务筛选。如果路径数量爆炸就必须在松弛逻辑里加权重因子或者用多目标Dijkstra变体。总之“求路径”从来不是把算法跑完就结束而是要和业务判定标准绑在一起。5. 实测中容易踩的坑与应对方法5.1 INF选不好代码直接溢出这是最隐蔽的问题。以前我用int存距离时图里边的权重一旦到10^9两个边迭加就会超过2^31-1出现负数而负的距离值会彻底摧毁Dijkstra里的贪心逻辑——明明该走最短路径因为溢出出现了“更短”的鬼路径结果全图乱套。现在的做法是统一用long longINF 1e18。这个值足够大保证dist[u] w在这个量级下不会溢出同时又不至于大到和真实距离混淆。我还见过用INT_MAX / 2当无穷大的保守策略也可以但long long更稳完全不存在加法后爆掉的问题。5.2 重边和多条边的去与留一个图上两个节点之间可能出现多条边权重还不一样。如果图是邻接矩阵存的后赋值的边会覆盖前面的边这时候必须在读入时取最小值g[u][v] min(g[u][v], w);如果图是邻接表存的中规中矩不取最小值也不至于错——Dijkstra松弛时会逐一比较更小的那条自然会被选中。但如果边的数量很大每次都让两条边都参与松弛会增加常数开销。所以我习惯在读图时就顺手去重能省则省。无向图尤其要注意加边时要同时推入adj[u]和adj[v]我曾经因为忘记加反向边排查了半天路径总是不对。5.3 优先队列里的陈旧条目一定记得跳过第3.2节里if (d ! dist[u]) continue;这一行很多人初学时觉得可有可无。我可以负责任地告诉你它不仅仅是优化是正确性和复杂度的双重保险。假设某个节点被更新了很多次优先队列里存了5个它的条目最坏情况下堆里条目数量会达到所有松弛操作的次数也就是O(E)。如果图有10^5条边堆里可能出现几十万个元素每次弹出都是O(log E)整体还会退化到接近O(E log E)虽然不至于错但性能会明显劣化。更重要的是陈旧条目如果不跳过可能带来奇怪的行为一个节点已经被确定后来从过期条目又取出一个较大的d去执行松弛操作虽然不会导致错误结果因为松弛时dist[u]w dist[v]很难成立但白白浪费了大量时间。跳过陈旧条目的正确姿势就是比较距离值。还有一种常见写法是维护visited数组每个节点只处理第一次弹出也能达到同样效果我自己更习惯用距离值比较因为少一个数组更清爽。5.4 不要试图硬上负权边Dijkstra对负权边是无效的这一点必须时刻刻在心里。我见过有人在网上争论“用Dijkstra能不能处理负权”结论很干脆不能。原因还是贪心假设——负权边会制造一种“先绕路再倒贴”的路径使得某个本来距离很大的节点突然变成最优候选而之前已经确定过的节点可能需要被重新确定。算法不会回头所以必然出错。如果图里有负权边直接换Bellman-Ford或者队列优化的SPFA。SPFA在多数随机图中很快但最坏复杂度没有保证面试时想稳就提Bellman-Ford。这里就不展开讲了你只要记住Dijkstra的适用边界。5.5 大量节点时的内存与建图选择用邻接矩阵开数组n10^5时矩阵就是10^10个位置直接爆内存。工程图和竞赛图都偏向稀疏图所以默认用邻接表存储vectorvectorpairint, long long。C如果担心vector扩容大量搬移可以预分配每个顶点vector的容量或者用vectorpair直接用整体性能在大多数场景都够用。我之前做过一个n2e5、m5e5的随机图测试堆优化版Dijkstra总耗时大约在0.3秒到0.6秒区间具体看机器和常数完全可接受。6. 从Dijkstra走向更复杂的场景6.1 双向Dijkstra起点终点都知道时省一半力气如果只需要求“某两个点之间的最短路径”而不是从源点出发去所有点可以用双向Dijkstra从起点和终点同时各跑一轮单向Dijkstra当两个方向的搜索区域相遇时停止。这样搜索的半径变小实测在随机图上可以省约一半甚至更多的松弛操作。实现时两个方向各维护一套dist和优先队列。当某个节点u同时被两边访问到时就以dist1[u] dist2[u]为候选答案并在两边继续扩张的过程中更新最小值。终止条件不是简单相遇而是两边弹出的最小距离之和已经大于等于当前候选答案这样就不会错过更优路径。我第一次写双向Dijkstra时犯了终端判断的错误结果跑出来的路径不是最优后来加了一条“候选答案单调更新且两边优先队列顶部距离之和 当前候选答案就退出”的条件问题才解决。6.2 引入A*加一个启发式估计加速搜索当你不仅知道终点还能估计“当前点到终点的最小剩余代价”时Dijkstra的优先队列排序不再只按实际距离dist[u]而按dist[u] h[u]来排。这里的h[u]是启发函数只要能保证不高于真实剩余距离可采纳性得到的答案依然是最优的这就是A*算法。在很多网格路径规划场景中用曼哈顿距离作为h[u]效果非常好。相比纯DijkstraA会更早地朝终点方向探索减少无关区域的松弛操作。但要注意如果你的图结构不规则、不好设计可采纳的启发函数A的收益就不明显此时老老实实用双向Dijkstra往往更稳。6.3 动态权重的处理思路工程中图的边权经常是动态变化的比如实时交通路况会影响通行时间。这类问题严格说已经超出静态Dijkstra的范畴。常见做法是定期用实时数据重建权重然后重新执行Dijkstra更复杂一点是维护一颗最短路径树在权重变化时只局部更新。后者实现复杂度高连通性和性能权衡也要仔细测试普通项目先用重建法即可没必要为了优化而优化。从我自己的实践来看先精通静态Dijkstra的每一个细节再往动态场景扩展是效率最高的学习路径。跳过基础直接追高级变体最后遇到基础实现错误时反而要回头花费大量时间排查。提示如果你写完的Dijkstra在随机小图上测试正确但一到大图就卡住90%的原因是优先队列里的过时条目没有跳过先去检查那个continue写没写。7. 一些工程化的调试技巧7.1 小图日志手工打印每一步调试Dijkstra时我特别推荐一种“逐步打印”的方式。在每次从优先队列弹出一个节点并确定后打印出当前dist数组的完整变化过程和松弛边这样就能很清楚地看到贪心顺序是否正确。下面是一个简单的调试打印示例void print_debug_state(int u, const vectorlong long dist) { cout 确定节点 u 当前 dist ; for (auto d : dist) { if (d INF) cout INF ; else cout d ; } cout \n; }在小图上人眼比对能快速发现某个节点的距离被错误地更新成非最优值这时再去查贪心顺序和边权读取是否对称基本能找到问题。7.2 对拍验证用一个暴力算法做裁判在给任何大图跑算法之前我都建议写一个最朴素的暴力BFS或Floyd-Warshall做基准。对拍是指随机生成一个小规模图比如n 8同时跑Dijkstra和暴力算法比较每个节点的最短距离是否一致。只要随机生成几百组不重样的小图几乎能测出所有边界问题包括起点孤立、目标不可达、多条边权重相同等。这种对拍脚本本身很简单却能节省大量手动造数据的时间。我现在每次实现图论算法都会先写一个验证小工具等它跑通了再正式在线提交或投入业务。7.3 面向竞赛与面向工程代码组织的差异竞赛里的Dijkstra往往是单文件、面向AC来的工程里则要关注可读性、可维护性和内存占用。我的习惯是把图构建、Dijkstra计算、路径还原拆成三个独立函数并用一个struct Edge封装边信息而不是到处裸写pair。在代码评审时可读性比少写两行重要得多。另外注意变量命名别用太简单的dis、pre至少在工程代码里写全distanceVector、predecessor这类名称。这点小小习惯能帮你在一周后回看代码时依旧秒懂。对初学者来说把变量名写清楚本身就是一种“注释”。8. 我实际项目中用过的一个完整示例我去年参与过一个内部的配送路径优化模拟项目需求简单说就是一张配送网络有几千个站点每个站点之间的运输时间是已知的需要用Dijkstra计算任意配送站到客户点的最短时间路径。核心模块我就按第3.2节的模板写的只是数据结构上做了些封装。为了让你能直接抄作业我整理了一个带路径还原的最小可运行版本#include bits/stdc.h using namespace std; const long long INF 1e18; struct Result { vectorlong long dist; vectorint pre; }; Result dijkstra(int src, const vectorvectorpairint, long long adj) { int n adj.size(); Result res; res.dist.assign(n, INF); res.pre.assign(n, -1); res.dist[src] 0; priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! res.dist[u]) continue; for (auto [v, w] : adj[u]) { if (res.dist[u] w res.dist[v]) { res.dist[v] res.dist[u] w; res.pre[v] u; pq.emplace(res.dist[v], v); } } } return res; } void show_path(int src, int target, const vectorint pre) { if (target src) { cout src; return; } show_path(src, pre[target], pre); cout - target; } int main() { int n 5; vectorvectorpairint, long long adj(n); auto add_edge [](int u, int v, long long w) { adj[u].push_back({v, w}); }; add_edge(0, 1, 4); add_edge(0, 2, 2); add_edge(2, 1, 1); add_edge(1, 3, 5); add_edge(2, 3, 8); add_edge(3, 4, 3); Result res dijkstra(0, adj); for (int i 0; i n; i) { cout dist[0- i ] res.dist[i] \n; } cout 最短路径: ; show_path(0, 4, res.pre); cout \n; return 0; }运行输出大致是dist[0-0] 0 dist[0-1] 3 dist[0-2] 2 dist[0-3] 8 dist[0-4] 11 最短路径: 0 - 2 - 1 - 3 - 4这个版本去掉注释也就四十来行无论是面试手写、竞赛模板还是项目内部轮子拿来当起点都够用。以后在这个基础上扩展双向搜索或A*需要改动的部分也很集中优先队列排序的键值、终止条件也就这两处。最后说一个我自己反复踩过的地方调试Dijkstra时千万不要只盯着目标节点的距离值看要观察整个dist数组的变化过程。因为Dijkstra的贪心过程是全局性的某个看似无关的节点被错误更新最后可能绕远路影响目标结果。写日志的时候把整个数组打出来问题往往一眼就看清了。