1. 从一道题看单源最短路的本质1.1 这道题到底在问什么“追债之旅”这个标题乍一看像是社会新闻实际上它是一道典型的图论题目核心考点就一个单源最短路。题目的场景大致是这样的——你是一个债主要从起点城市出发去若干个城市追讨欠款城市之间有一些道路连接每条路有通行成本时间、金钱或者体力问你怎么走才能用最小的代价到达目标城市。这类题在算法竞赛和面试中出现的频率极高因为它的模型足够简单但变体足够多。简单在于给定一张图给定一个起点求到其他所有点的最短路径。复杂在于图的规模、边权的性质、是否有负权边、是否需要输出路径、是否有多个终点……每一个条件的变化都会导致你选择的算法完全不同。我见过太多人一看到“最短路”三个字就直接上Dijkstra结果遇到负权边直接崩掉也见过有人不管数据规模上来就Floyd三重循环结果n100000的时候直接超时。所以这篇文章不只是讲这一道题怎么做而是借这道题把单源最短路的整个知识体系给你串一遍。1.2 谁适合看这篇内容如果你正在准备算法竞赛或者正在刷题准备面试这篇内容对你来说应该是刚需。具体来说已经学过图论基础知道邻接矩阵和邻接表怎么建但对最短路算法的选择没有把握的人能写出Dijkstra的模板代码但说不清楚为什么不能处理负权边的人遇到题目变体比如多终点、带约束、需要输出路径就不知道从何下手的人想系统梳理单源最短路知识体系把Dijkstra、Bellman-Ford、SPFA、堆优化等知识点串起来的人。如果你是完全零基础连图是什么都不知道那建议先补一下图的基本概念——顶点、边、有向图、无向图、权值这些。不过我也会尽量用生活化的例子来解释所以即使基础薄弱跟着读下来也能理解个七八成。2. 单源最短路的核心算法选型2.1 为什么算法选型是最关键的一步单源最短路问题有很多种解法但没有任何一种算法是万能的。选错算法的后果很直接要么答案错误要么超时。我个人的经验是拿到题目之后不要急着写代码先花两分钟确认三件事边权是正数还是可能有负数这决定了你能不能用Dijkstra。图的规模有多大n和m的范围决定了你该用O(n²)的还是O(m log n)的算法。需要求什么只求到某一个点的距离还是求到所有点的距离需不需要记录路径这三个问题确认清楚了算法基本就定下来了。下面我把几种常见的单源最短路算法做一个对比你可以直接对照着选。2.2 四种核心算法对比算法适用条件时间复杂度能否处理负权边能否处理负环Dijkstra朴素非负权边O(n²)否否Dijkstra堆优化非负权边O(m log n)否否Bellman-Ford任意权边O(nm)是能检测SPFA任意权边平均O(km)最坏O(nm)是能检测这张表建议你记住面试的时候经常问。我展开说一下每个算法的核心逻辑和适用场景。Dijkstra的核心思想是贪心。它维护一个已确定最短路的点集每次从尚未确定的点中选出当前距离最小的那个然后用它去松弛它的邻居。为什么不能有负权边因为贪心的前提是“当前最小的距离不会再被更新”但如果存在负权边后面可能出现一条更短的路把之前的结论推翻。举个例子A到B的距离是3A到C的距离是5C到B的距离是-3。按照Dijkstra先确定B的距离是3但实际上A→C→B的距离是5(-3)2比3更小。所以Dijkstra在负权边面前直接失效。Bellman-Ford的核心思想是动态规划。它对所有边进行n-1轮松弛每一轮都尝试用每条边去更新终点的距离。n-1轮之后如果还能松弛说明存在负环。它的好处是能处理负权边坏处是时间复杂度太高O(nm)在n和m都上千的时候就已经很吃力了。SPFA是Bellman-Ford的队列优化版本。它不再盲目地对所有边做n-1轮松弛而是用一个队列维护“距离被更新过的点”只对这些点的出边做松弛。平均情况下效率很高但最坏情况下会被卡到O(nm)。竞赛中如果出题人故意构造数据SPFA是很容易被卡的。所以如果边权非负优先用堆优化的Dijkstra稳定O(m log n)。2.3 这道题应该选哪个算法回到“追债之旅”这道题。根据题目描述边权代表的是通行成本通常是正数时间、距离、花费不可能为负。所以首选堆优化的Dijkstra。如果题目没有明确说边权非负但数据规模不大n≤1000用SPFA也可以。但如果n和m都到了10⁵级别那就必须用堆优化Dijkstra否则大概率超时。我个人的习惯是只要边权非负无脑上堆优化Dijkstra。模板写熟了之后写一次也就五六分钟的事而且不容易出错。SPFA虽然代码更短但被卡的风险始终存在竞赛中能不用就不用。3. 堆优化Dijkstra的完整实现与细节拆解3.1 核心数据结构的选择堆优化Dijkstra需要两个核心数据结构邻接表和优先队列。邻接表用来存图。为什么不用邻接矩阵因为邻接矩阵的空间复杂度是O(n²)当n10⁵的时候光开数组就爆内存了。邻接表的空间复杂度是O(nm)只存实际存在的边适合稀疏图。竞赛中的图绝大多数都是稀疏图所以邻接表是标配。优先队列用来每次取出当前距离最小的点。C中用priority_queueJava中用PriorityQueuePython中用heapq。需要注意的是priority_queue默认是大根堆我们需要小根堆所以存入的时候要把距离取负或者自定义比较器。3.2 邻接表的两种写法邻接表有两种常见的实现方式vector数组和链式前向星。vector数组的写法更直观适合大多数场景vectorpairint, int adj[N]; // adj[u]存储{终点v, 边权w} // 添加一条从u到v权值为w的边 adj[u].push_back({v, w});链式前向星的写法更底层速度略快但代码可读性差一些int head[N], to[M], nxt[M], w[M], cnt 0; void addEdge(int u, int v, int weight) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; }我一般用vector数组因为可读性好调试方便而且现代编译器的优化已经让两者的性能差距很小了。除非题目卡常数卡得特别死否则没必要用链式前向星。3.3 堆优化Dijkstra的完整代码下面是一份可以直接抄的模板我加了详细注释#include bits/stdc.h using namespace std; const int N 100010; // 最大点数 const int INF 0x3f3f3f3f; // 无穷大用0x3f3f3f3f的好处是相加不会溢出 vectorpairint, int adj[N]; // 邻接表 int dist[N]; // 起点到每个点的最短距离 bool visited[N]; // 是否已经确定最短路 int n, m, s; // n个点m条边起点为s void dijkstra(int start) { // 初始化 memset(dist, 0x3f, sizeof(dist)); memset(visited, 0, sizeof(visited)); dist[start] 0; // 小根堆存储{距离, 点编号} priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 如果这个点已经确定过了跳过 if (visited[u]) continue; visited[u] true; // 松弛所有出边 for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { cin n m s; for (int i 0; i m; i) { int u, v, w; cin u v w; adj[u].push_back({v, w}); // 如果是无向图加上下面这行 // adj[v].push_back({u, w}); } dijkstra(s); for (int i 1; i n; i) { if (dist[i] INF) cout 不可达 ; else cout dist[i] ; } return 0; }这段代码有几个细节值得展开说。3.4 三个容易踩坑的细节第一个坑visited数组的作用。很多人写堆优化Dijkstra的时候不加visited数组也能跑出正确答案但效率会打折扣。原因是同一个点可能被多次压入优先队列每次距离被更新都会压入一次如果不加visited判断就会重复处理同一个点的出边。加了visited之后每个点只会被处理一次效率更高。注意visited是在出队的时候判断不是在入队的时候判断这一点和BFS不同。第二个坑INF的取值。用0x3f3f3f3f而不是INT_MAX原因是0x3f3f3f3f 0x3f3f3f3f 0x7e7e7e7e没有超过int的范围不会溢出。而如果用INT_MAX加上任何正数都会溢出变成负数导致松弛判断出错。这个细节在竞赛中非常关键我见过不止一个人因为这个问题调了半天。第三个坑优先队列的排序方式。priority_queue默认是大根堆如果你直接存{dist, u}每次取出来的是距离最大的点完全违背了Dijkstra的贪心策略。解决办法有两种一是用greater比较器变成小根堆上面的代码用的就是这种二是存入{-dist, u}取出时再取负。两种方式都可以我习惯用第一种更直观。提示如果你用的是Pythonheapq本身就是小根堆直接存(dist, u)即可不需要额外处理。但要注意Python的heapq不支持自定义比较器如果距离相同需要比较点编号可以存(dist, u)这样的元组Python会自动按第一个元素排序第一个相同则按第二个排序。4. 从模板题到变体题的进阶思路4.1 多终点问题怎么处理“追债之旅”这类题目有时候会问从起点出发到多个目标城市中的任意一个最短距离是多少这种多终点问题其实不需要对每个终点都跑一遍Dijkstra只需要跑一次然后从所有终点的dist值中取最小值即可。因为Dijkstra跑完之后起点到所有点的最短距离都已经算出来了查表就行。如果题目反过来问从多个起点出发到一个终点的最短距离有一个技巧反向建图。把所有的边方向反过来然后从终点跑一次Dijkstra得到的dist数组就是所有点到终点的最短距离。这个技巧在多源问题中非常实用能把时间复杂度从O(k·m log n)降到O(m log n)。4.2 需要输出路径怎么办有些题目不仅要求最短距离还要求输出具体走的是哪条路径。这时候需要在Dijkstra的过程中记录每个点的前驱节点。具体做法是加一个pre[N]数组在松弛成功的时候更新pre[v] u。最后从终点沿着pre数组往回走就能还原出整条路径。int pre[N]; // 记录前驱节点 // 在松弛成功的地方加上 if (dist[u] w dist[v]) { dist[v] dist[u] w; pre[v] u; pq.push({dist[v], v}); } // 还原路径从终点t往回走 vectorint path; for (int cur t; cur ! -1; cur pre[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); // path中存储的就是从起点到终点的完整路径注意pre数组要初始化为-1起点的pre也设为-1这样循环到起点时自然结束。4.3 带约束条件的最短路有些题目会在最短路上加一些约束比如“最多只能经过k条边”、“必须经过某个点”、“每条边的费用不能超过某个值”等等。这类问题统称为约束最短路处理方式因题而异。以“最多经过k条边”为例这时候Dijkstra就不太适用了因为Dijkstra的贪心策略不考虑边数限制。正确的做法是用Bellman-Ford的思想做k轮松弛每一轮代表经过一条边。或者用分层图的思路把每个点拆成k1个状态分别表示经过0条边、1条边、…、k条边到达该点然后在新图上跑Dijkstra。分层图是一个非常重要的技巧很多看起来复杂的最短路变体都可以用分层图来建模。核心思想就是把状态维度加到图里面每个状态是一个节点状态之间的转移是一条边。这样就把约束条件转化成了图的结构直接套最短路模板就行。4.4 负权边和负环的处理如果题目中出现了负权边Dijkstra就不能用了得换Bellman-Ford或者SPFA。Bellman-Ford的代码更简单但效率低SPFA效率高一些但最坏情况会被卡。Bellman-Ford的核心代码就几行// 边集数组 struct Edge { int u, v, w; } edges[M]; int dist[N]; bool bellman_ford(int start, int n, int m) { memset(dist, 0x3f, sizeof(dist)); dist[start] 0; // n-1轮松弛 for (int i 1; i n; i) { bool updated false; for (int j 0; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[u] w dist[v]) { dist[v] dist[u] w; updated true; } } if (!updated) break; // 提前退出优化 } // 第n轮检查负环 for (int j 0; j m; j) { int u edges[j].u, v edges[j].v, w edges[j].w; if (dist[u] ! INF dist[u] w dist[v]) { return false; // 存在负环 } } return true; }那个updated标记是一个实用的优化如果某一轮没有任何点的距离被更新说明已经收敛了后面的轮次可以跳过。这个优化在大多数情况下能显著减少运行时间。注意判断负环的条件是“第n轮仍然能松弛”而不是“某个点的距离变成了负数”。负环的含义是总权值为负的环不是某条边的权值为负。这个区别在面试中经常被问到。5. 常见问题与排查技巧实录5.1 答案错误类问题问题一输出的距离全部是INF或者0x3f3f3f3f。这种情况通常是图没有建对。排查步骤先检查边的输入格式是否和题目一致是有向边还是无向边再检查邻接表的索引是否从1开始如果题目给的点编号是1到n你的数组也要从1开始。如果用的是无向图但只加了一个方向的边也会导致部分点不可达。问题二部分点的距离正确部分点的距离偏大。大概率是松弛条件写错了。正确的松弛条件是dist[u] w dist[v]不是。用会导致距离相同的点被重复入队虽然不影响最终答案但会降低效率。另外检查一下w是否用对了有些题目边的权值在输入中的位置比较特殊容易读错。问题三有负权边但用了Dijkstra答案偏大。这是算法选型错误没有别的办法换Bellman-Ford或SPFA。判断方法如果题目中出现了“费用可能为负”、“收益”、“补贴”这类字眼就要警惕负权边的存在。5.2 超时类问题问题一用了朴素Dijkstran10⁵直接超时。朴素Dijkstra的时间复杂度是O(n²)n10⁵的时候就是10¹⁰次操作肯定超时。换成堆优化版本复杂度降到O(m log n)10⁵级别的数据轻松跑过。问题二用了SPFA被卡超时。SPFA的最坏时间复杂度是O(nm)出题人如果故意构造网格图或者菊花图很容易把SPFA卡到最坏情况。解决办法如果边权非负换堆优化Dijkstra如果确实有负权边考虑用Bellman-Ford加队列优化或者用Johnson算法先跑一次Bellman-Ford处理负权再用Dijkstra。问题三优先队列中压入了太多重复元素导致内存超限。每个点每次距离被更新都会压入一次最坏情况下队列中可能有m个元素。对于m10⁶的题目队列可能占用较大内存。优化方法加visited数组出队时如果已经访问过就跳过或者用配对堆、斐波那契堆等更高级的数据结构但一般竞赛中不需要。5.3 常见问题速查表问题现象可能原因排查方法解决方案全部输出INF图未正确建立检查边的方向和索引确认有向/无向检查数组下标部分点距离偏大松弛条件错误检查是否用了而非改为严格小于负权边答案错误算法选型错误检查是否有负权边换Bellman-Ford或SPFAn10⁵超时用了朴素Dijkstra看时间复杂度换堆优化版本SPFA被卡出题人构造了最坏数据看数据规模换堆优化Dijkstra内存超限优先队列元素过多检查是否有visited优化加visited数组路径输出错误pre数组未初始化检查pre的初始值初始化为-15.4 几个实战中总结的避坑技巧技巧一先写暴力再优化。如果时间允许先写一个O(n²)的朴素版本确认答案正确之后再改成堆优化版本。这样可以把“算法逻辑错误”和“优化引入的bug”分开排查效率更高。技巧二用小数据对拍。自己造几组小数据n≤5用手算验证答案然后和程序输出对比。这个方法虽然笨但非常有效尤其是调试路径输出类问题的时候。技巧三注意数据范围。如果n和m到了10⁶级别即使用了堆优化Dijkstra也可能因为常数太大而超时。这时候可以考虑用链式前向星代替vector用scanf/printf代替cin/cout用快读快写优化输入输出。这些常数优化在卡时间的题目中往往是决定性的。技巧四多源问题反向建图。如果题目要求“从多个起点到某个终点的最短距离”不要对每个起点都跑一遍Dijkstra直接把边反向从终点跑一次就行。这个技巧能帮你省下大量时间。技巧五注意重边和自环。有些题目中两个点之间可能有多条边或者存在自环。Dijkstra本身能处理重边取最小的那条即可但自环如果权值为正不影响结果如果权值为负则构成负环。建图的时候不需要特殊处理算法本身能应对。6. 单源最短路的扩展应用场景6.1 竞赛中的常见变体单源最短路在竞赛中的变体非常多我列举几个常见的最短路计数不仅要求最短距离还要求有多少条路径能达到最短距离。做法是在Dijkstra松弛的时候如果发现更短的距离更新计数为1如果发现距离相等计数累加。次短路求第二短的路。做法是每个点维护两个距离最短和次短在松弛的时候同时更新这两个值。K短路求第K短的路。一般用A*算法或者可持久化左偏树难度较高。最短路树把所有点的pre边拿出来构成一棵树。这棵树有很多有趣的性质比如树上任意点到根的距离就是最短距离。6.2 实际工程中的应用单源最短路不仅仅是竞赛题在实际工程中也有大量应用地图导航从起点到终点的最短路径规划就是最短路问题的直接应用。实际中还会考虑实时路况、转弯限制等因素但核心算法还是Dijkstra及其变体。网络路由数据包在网络中传输时路由器需要选择一条最短路径。OSPF协议用的就是Dijkstra算法。社交网络计算两个人之间的最短关系链六度分隔理论本质上是无权图的最短路用BFS即可。任务调度某些任务之间存在依赖关系求完成所有任务的最短时间可以转化为最短路问题。6.3 从这道题能学到什么“追债之旅”这道题表面上是一道模板题但它背后的知识体系非常庞大。通过这道题你应该掌握单源最短路的四种核心算法及其适用条件堆优化Dijkstra的完整实现和三个关键细节多终点、路径输出、负权边等常见变体的处理方式常见错误的排查思路和避坑技巧。这些知识点不仅在竞赛中有用在面试和实际工程中也是基本功。我个人的建议是把堆优化Dijkstra的模板背熟做到不看参考就能写出来然后理解Bellman-Ford和SPFA的原理知道什么时候该用它们最后通过刷题积累变体的处理经验。我在实际刷题中的体会是最短路问题的难点从来不是算法本身而是建模——如何把题目描述转化为图论模型。这需要大量的练习和总结。每做完一道题花几分钟想一想这道题的核心考点是什么如果条件变了该怎么处理有没有更优的解法这样积累下来遇到新题的时候就能快速找到思路。最后分享一个小技巧如果你在比赛中遇到最短路问题但不确定该用哪个算法可以先看一眼数据范围。n≤100用Floydn≤1000用朴素Dijkstran≤10⁵用堆优化Dijkstra有负权边用SPFA或Bellman-Ford。这个经验法则能帮你在短时间内做出正确的选择。