1. 从地图导航说起为什么我们需要Dijkstra算法想象一下你正站在一个巨大的十字路口面前有无数条岔路通向未知的目的地。你的手机导航App告诉你到达朋友家需要25分钟而避开拥堵的另一条路线则需要30分钟。你有没有想过这个精确到分钟的预估时间背后是谁在默默计算没错在很多情况下正是我们今天要聊的主角——Dijkstra算法在发挥作用。我第一次接触这个算法不是在什么高深的论文里而是在一个真实的项目里。当时我们需要为一个园区内的无人配送小车规划最短行驶路径。地图上有几十个配送点点与点之间道路的“成本”不仅仅是距离还有通过时间、路面状况等等。我一开始尝试用最笨的方法让小车把所有可能的路都“想”一遍结果代码跑起来慢得让人绝望。直到一位前辈拍了拍我肩膀说“试试Dijkstra吧这是找最短路的‘老黄牛’虽然朴实但绝对可靠。”那么Dijkstra算法到底是什么呢简单说它是一个用来解决“单源最短路径”问题的贪心算法。这个名字听起来有点唬人咱们拆开看“单源”意思是只有一个起点“最短路径”就是找出从这个起点到图中所有其他点的最短距离。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出堪称图论领域的基石之一。它的核心规矩是图上所有边的权重你可以理解为距离、时间、成本必须是非负数。这很符合直觉你总不会遇到一条路走上去能让你的总路程减少吧当然现实中如果有这样的“虫洞”那得用别的算法了。这个算法的思想非常“聪明”且“人性化”。它模拟了一个有耐心的人一步步探索未知地图的过程每次只从当前已知的、离起点最近的那个路口出发去探索它周围的新路口并更新这些新路口到起点的最短距离。就这样以起点为圆心最短的路径像水波一样一圈一圈地扩散出去直到覆盖所有目的地。这个过程里有两个关键动作“找最近点”和“松弛操作”。前者决定了下一步探索哪里后者则负责更新和优化已知的路径信息。2. 第一步用邻接矩阵实现最朴素的Dijkstra理解了算法在干什么我们就要动手把它变成代码。对于初学者或者当我们的图规模不大比如节点数在500以内时最直观、最容易理解的方式就是使用邻接矩阵。2.1 邻接矩阵一张巨大的“城市公交表”什么是邻接矩阵你可以把它想象成一张巨大的、N行N列的表格N是节点数。如果我想知道从“A点”到“B点”有没有路路有多长我只需要查表格的第A行、第B列那个格子就行了。有路格子里就写着距离没路格子就是0或者一个特殊值比如无穷大。const int MAX_N 510; // 假设最多500个节点留点余量 int graph[MAX_N][MAX_N]; // 邻接矩阵初始化这张表的时候我们通常把每个格子都设为一个很大的数比如0x3f3f3f3f一个接近int上限的值用来模拟“无穷远”表示一开始我们认为所有点之间都不通。然后每读入一条从u到v、权重为w的边我们就在graph[u][v] w。如果是无向图别忘了对称地设置graph[v][u] w。这种方法的优点是一目了然访问任意两点间有没有边、边权多少速度是O(1)快极了。但缺点也显而易见太占地方了。如果我有1000个节点哪怕只有2000条边这已经是稀疏图了我也需要开辟一个1000*1000的矩阵里面绝大部分空间存储的都是“无穷大”浪费严重。这就是所谓的空间复杂度 O(V²)。2.2 核心循环手动寻找“最近的前线据点”有了地图邻接矩阵算法就可以开始了。我们需要三个帮手dist[]数组记录从起点到每个点的当前已知最短距离。初始化时起点设为0其他点都是无穷大。visited[]数组标记一个点是否已经找到了最终确定的最短路径。一旦确定就不再改动。一个循环这个循环要执行V次V是节点数因为我们要逐个确定每个点的最短路径。每次循环里我们都要做一件“苦力活”遍历所有节点从那些还没确定最短路径visited为假的节点中找出dist值最小的那一个。这个点就是当前离起点最近的“前线据点”。int t -1; // t用来记录当前找到的“最近点” for (int j 1; j n; j) { if (!visited[j] (t -1 || dist[j] dist[t])) { t j; } } // 找到后标记它为已确定 visited[t] true;找到这个“据点”t后我们就以此为基础进行扩张。遍历t的所有邻居在邻接矩阵里就是遍历第t行尝试进行“松弛操作”如果从起点先到t再从t到邻居j的距离比之前记录的到j的距离更短那就更新它。for (int j 1; j n; j) { // 如果t和j之间没有边graph[t][j]是无穷大跳过 if (graph[t][j] INF) continue; // 松弛操作 if (dist[j] dist[t] graph[t][j]) { dist[j] dist[t] graph[t][j]; } }我把这种实现方式称为“朴素Dijkstra”。它的时间复杂度是 O(V²)因为外层循环V次内层每次都要花O(V)的时间去找最小dist。在节点数不多的时候它简单可靠是理解算法本质的绝佳起点。但就像我那个无人小车项目当节点数上到几千、几万这个 O(V²) 的复杂度就会成为性能瓶颈程序会慢得无法接受。这时候我们就必须请出优化神器——优先队列。3. 性能瓶颈与救星优先队列登场让我们仔细审视一下朴素版本中最耗时的部分每一轮我们都要扫描所有未确定的节点找出dist最小的那个。这就像一个经理每次要派活时都得把全公司几百号员工的名册从头到尾看一遍找出最闲的那个。活少的时候还行员工节点一多经理的时间全花在“找人”上了效率极低。有没有一种办法能让我们随时快速拿到那个“最闲的员工”距离最小的节点呢有这就是优先队列Priority Queue特别是最小堆Min Heap数据结构。它就像一个智能的待办事项列表总是把当前最重要这里指距离最小的任务放在最上面让你一眼就能拿到。3.1 优先队列如何颠覆查找过程使用优先队列后我们的算法流程会发生一个美妙的变化我们不再需要visited数组吗不我们仍然需要但作用略有不同。我们不再需要手动循环查找最小dist节点。我们只需要从优先队列的队头堆顶取出一个节点它极有可能就是当前距离最小的节点。关键点在于同一个节点可能会被多次加入优先队列因为它的dist被多次更新每次更新都认为找到了更短的路径就重新入队。所以当我们从队列中取出一个节点时需要检查这个节点当前记录在dist数组中的值是否等于我们当初把它放进队列时附带的值即当时的距离或者更简单地如果这个节点已经被处理过了visited为真我们就直接跳过它。这个操作叫做“懒惰删除”。这样一来查找最小节点的复杂度从 O(V) 骤降到了 O(log V)因为从堆顶取元素是 O(1)但取出后调整堆需要 O(log V)。整个算法的时间复杂度就优化到了O((VE) log V)其中E是边数。对于稀疏图E远小于 V²这个提升是指数级的。3.2 C STL中的priority_queue实战技巧C标准库提供了priority_queue但它默认是一个最大堆大的元素优先级高。我们需要的是最小堆怎么办呢有几种经典“骚操作”方法一存入负数利用最大堆特性。这是最直接也最常用的技巧。既然我们要按距离从小到大取而它默认从大到小取那我们就把距离取负号存进去。这样距离最小的比如3取负后-3反而最大就会被放在堆顶。priority_queuepairint, int pq; // 默认最大堆 // 存入时存 {-distance, node} pq.push({-dist[neighbor], neighbor}); // 取出时距离需要再取负恢复 int current_dist -pq.top().first; int current_node pq.top().second;方法二自定义比较器。这种方法更清晰但写起来稍长。我们声明一个最小堆// 使用greater作为比较函数让小的优先 priority_queuepairint, int, vectorpairint, int, greaterpairint, int min_pq; min_pq.push({dist[neighbor], neighbor}); // 这时可以直接存正数在实际项目中我两种都用过。如果图非常复杂操作频繁方法二在逻辑上更清晰不容易出错。如果是竞赛或者快速原型开发方法一写起来更快。我个人的习惯是在团队协作的项目里用方法二自己写小工具时用方法一。4. 空间优化大师从邻接矩阵到邻接表用了优先队列我们优化了“找节点”的时间。但别忘了朴素版本还有一个大问题邻接矩阵太占空间。当节点数达到10^5级别时一个10^5 * 10^5的矩阵内存直接就爆了。我们必须换一种更紧凑的存储图的方式——邻接表。4.1 邻接表只记录真实存在的道路邻接表的思路非常节俭我不再关心“从A到B有没有路”这个布尔问题而是只为每个节点A维护一个列表这个列表里只记录从A真正能到达的邻居B以及这条边的权重。在C中实现邻接表最常用的方式是使用“数组模拟链表”或者直接使用vector套pair。数组模拟链表效率极高是竞赛中的常客而vector版本则更易读易懂。数组模拟链表版链式前向星const int MAX_EDGES 2e5 7; // 注意这里大小是边数的两倍无向图 int head[MAX_NODES]; // head[u]节点u的第一条边的编号 int edge_to[MAX_EDGES]; // edge_to[i]第i条边指向的节点 int edge_weight[MAX_EDGES]; // edge_weight[i]第i条边的权值 int edge_next[MAX_EDGES]; // edge_next[i]第i条边的“下一条边”编号 int edge_cnt 0; // 边的计数器 // 加边函数 void add_edge(int u, int v, int w) { edge_cnt; edge_to[edge_cnt] v; edge_weight[edge_cnt] w; edge_next[edge_cnt] head[u]; // 新边指向u原来的第一条边 head[u] edge_cnt; // u的头边更新为新边 }遍历节点u的所有邻居时代码是这样的for (int i head[u]; i ! 0; i edge_next[i]) { int v edge_to[i]; int w edge_weight[i]; // 对邻居v进行操作边权为w }这种方式就像一串珠子head[u]是线头顺着edge_next指针就能摸到所有从u出发的边。Vector版本更推荐初学者使用vectorvectorpairint, int graph(MAX_NODES); // graph[u] 存储的是一个列表里面每个元素是pair邻居v, 边权w // 加边 graph[u].push_back({v, w}); // 如果是无向图还需要 graph[v].push_back({u, w}); // 遍历节点u的所有邻居 for (auto [v, w] : graph[u]) { // 对邻居v进行操作边权为w }vector版本写起来简洁明了几乎就是邻接表定义的直译。虽然在极端性能场景下可能略逊于数组模拟但在99%的工程和面试场景中完全够用且不易出错。我强烈建议新手先从vector版本入手彻底理解后再去看数组模拟的优化技巧。4.2 结合优先队列与邻接表的完整实现现在我们把两大优化结合起来用优先队列加速节点选取用邻接表高效存储图。这就是现代Dijkstra算法的标准形态足以应对绝大多数大规模稀疏图的最短路径问题。下面是一个使用vector邻接表和priority_queue的完整、健壮的实现#include iostream #include vector #include queue #include climits using namespace std; const int INF INT_MAX; // 用整型最大值表示无穷大 void dijkstra(int start, const vectorvectorpairint, int graph, vectorint dist) { int n graph.size(); dist.assign(n, INF); // 初始化所有距离为无穷大 dist[start] 0; // 使用最小堆存储 (距离, 节点) priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [current_dist, u] pq.top(); pq.pop(); // 关键懒惰删除。如果取出的距离大于当前记录的距离说明这是旧的、无效的条目跳过。 if (current_dist dist[u]) { continue; } // 遍历u的所有邻居 for (auto [v, weight] : graph[u]) { int new_dist dist[u] weight; if (new_dist dist[v]) { dist[v] new_dist; pq.push({new_dist, v}); // 将更优的路径加入队列 } } } } int main() { int n, m; // n节点m边 cin n m; vectorvectorpairint, int graph(n 1); // 节点编号从1开始 for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); // 如果是无向图取消下一行注释 // graph[v].push_back({u, w}); } vectorint dist; dijkstra(1, graph, dist); // 计算从节点1出发的最短距离 // 输出结果 for (int i 1; i n; i) { if (dist[i] INF) { cout Node i : Unreachable endl; } else { cout Node i : dist[i] endl; } } return 0; }这段代码有几个我踩过坑后总结的要点使用INT_MAX作为无穷大清晰且标准。但要注意做加法时可能溢出在严格场景下可以用0x3f3f3f3f这种足够大又不会溢出的数。明确的“懒惰删除”if (current_dist dist[u]) continue;这行是保证正确性和效率的灵魂。没有它算法可能会慢很多甚至在某些情况下出错。清晰的变量名graph,dist,u,v,weight。好的命名是最好的注释。使用C17的结构化绑定auto [v, weight]让遍历邻居的代码非常清爽。5. 不同场景下的选择与进阶思考掌握了标准版的Dijkstra你就能解决海量问题了。但真实世界总是更复杂一些我们需要根据不同的场景做选择和调整。5.1 稠密图 vs 稀疏图该用哪种实现这是一个常见的抉择。稠密图边数E接近V²的图。例如一个完全图每个点都和其他点相连。在这种情况下邻接矩阵的空间开销 O(V²) 是不可避免的因为边本身就这么多。此时朴素DijkstraO(V²)可能比堆优化版O(V² log V)更快因为堆操作带来的 log V 因子在V很大时会成为负担。我记得有一次处理一个大约有2000个节点的完全图用堆优化反而比朴素版慢了20%排查了好久才发现是这个原因。稀疏图边数E远小于V²的图。这是更常见的情况比如道路网、社交网络。堆优化邻接表的组合是绝对的主流和首选。如何判断一个粗略的经验法则是如果题目或数据明确提示节点数V很大5000但边数m相对不多那一定是稀疏图用优化版。如果不确定两种都实现一下用小规模数据测试对比是工程师的好习惯。5.2 不止于最短距离记录路径与处理多维度权重很多时候我们不仅要知道最短距离是多少还要知道怎么走。这就需要我们在进行松弛操作时额外记录一个predecessor前驱数组。vectorint prev(n1, -1); // 在松弛操作成功时 if (new_dist dist[v]) { dist[v] new_dist; prev[v] u; // 记录到达v的最短路径的上一个点是u pq.push({new_dist, v}); }算法结束后从终点t开始不断查找prev[t]就能倒推出整条路径。另一个进阶问题是多维度权重。比如路径成本同时包含“时间”和“金钱”我们想找时间最短的但在时间相同时找金钱最少的。这不再是简单的数值比较。一种方法是把成本和距离定义为一个结构体或pair然后自定义优先队列的比较函数让队列按照我们定义的复杂优先级来排序。这需要你对STL比较器有更深的理解但原理是相通的告诉优先队列什么叫做“更优”。5.3 算法的边界与替代者一定要牢记Dijkstra的“军规”边权不能为负。如果图中有负权边Dijkstra的贪心策略就会失效因为它假设“当前最短的路径就是最终最短的”而负权边可以让你走回头路来获得更短的距离这违背了前提。对于含负权边的图你需要使用Bellman-Ford算法或它的优化版SPFA算法。此外如果你需要求图中任意两点间的最短路径多源最短路而不是从一个固定起点出发那么跑V次Dijkstra是一种方法复杂度O(V*(VE)log V)但对于稠密图Floyd-Warshall算法O(V³)在编码复杂度上更有优势它基于动态规划代码极其简洁是处理小规模全源最短路的利器。从我第一次在项目里被性能问题卡住到后来能熟练地根据数据规模和图特性选择最合适的实现方式这个过程让我深刻体会到掌握一个算法不仅仅是背下它的模板代码更是理解它的内在逻辑、优势局限以及它与其他算法的关系。Dijkstra算法就像一把可靠的手术刀虽然不能解决所有问题但在它擅长的领域非负权图单源最短路它精准而高效。希望这次从邻接矩阵到优先队列的优化之旅能帮你不仅学会如何使用这把“手术刀”更能理解为何要这样打磨它。下次当你再看到导航App为你规划路线时或许你会会心一笑知道那背后是一段段优雅的代码和一个个像Dijkstra这样经典的算法在默默工作。