企业官网建设流程全解析

1. 从一道题看单源最短路的本质

1.1 这道题到底在问什么

“追债之旅”这个标题乍一看像是社会新闻，实际上它是一道典型的图论题目，核心考点就一个：单源最短路。题目的场景大致是这样的——你是一个债主，要从起点城市出发，去若干个城市追讨欠款，城市之间有一些道路连接，每条路有通行成本（时间、金钱或者体力），问你怎么走才能用最小的代价到达目标城市。

这类题在算法竞赛和面试中出现的频率极高，因为它的模型足够简单，但变体足够多。简单在于：给定一张图，给定一个起点，求到其他所有点的最短路径。复杂在于：图的规模、边权的性质、是否有负权边、是否需要输出路径、是否有多个终点……每一个条件的变化都会导致你选择的算法完全不同。

我见过太多人一看到“最短路”三个字就直接上Dijkstra，结果遇到负权边直接崩掉；也见过有人不管数据规模，上来就Floyd三重循环，结果n=100000的时候直接超时。所以这篇文章不只是讲这一道题怎么做，而是借这道题把单源最短路的整个知识体系给你串一遍。

1.2 谁适合看这篇内容

如果你正在准备算法竞赛，或者正在刷题准备面试，这篇内容对你来说应该是刚需。具体来说：

• 已经学过图论基础，知道邻接矩阵和邻接表怎么建，但对最短路算法的选择没有把握的人；
• 能写出Dijkstra的模板代码，但说不清楚为什么不能处理负权边的人；
• 遇到题目变体（比如多终点、带约束、需要输出路径）就不知道从何下手的人；
• 想系统梳理单源最短路知识体系，把Dijkstra、Bellman-Ford、SPFA、堆优化等知识点串起来的人。

如果你是完全零基础，连图是什么都不知道，那建议先补一下图的基本概念——顶点、边、有向图、无向图、权值这些。不过我也会尽量用生活化的例子来解释，所以即使基础薄弱，跟着读下来也能理解个七八成。

2. 单源最短路的核心算法选型

2.1 为什么算法选型是最关键的一步

单源最短路问题有很多种解法，但没有任何一种算法是万能的。选错算法的后果很直接：要么答案错误，要么超时。我个人的经验是，拿到题目之后不要急着写代码，先花两分钟确认三件事：

1. 边权是正数还是可能有负数？这决定了你能不能用Dijkstra。
2. 图的规模有多大？n和m的范围决定了你该用O(n²)的还是O(m log n)的算法。
3. 需要求什么？只求到某一个点的距离，还是求到所有点的距离？需不需要记录路径？

这三个问题确认清楚了，算法基本就定下来了。下面我把几种常见的单源最短路算法做一个对比，你可以直接对照着选。

2.2 四种核心算法对比

这张表建议你记住，面试的时候经常问。我展开说一下每个算法的核心逻辑和适用场景。

Dijkstra的核心思想是贪心。它维护一个已确定最短路的点集，每次从尚未确定的点中选出当前距离最小的那个，然后用它去松弛它的邻居。为什么不能有负权边？因为贪心的前提是“当前最小的距离不会再被更新”，但如果存在负权边，后面可能出现一条更短的路把之前的结论推翻。举个例子：A到B的距离是3，A到C的距离是5，C到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²)，当n=10⁵的时候，光开数组就爆内存了。邻接表的空间复杂度是O(n+m)，只存实际存在的边，适合稀疏图。竞赛中的图绝大多数都是稀疏图，所以邻接表是标配。

优先队列用来每次取出当前距离最小的点。C++中用priority_queue，Java中用PriorityQueue，Python中用heapq。需要注意的是，priority_queue默认是大根堆，我们需要小根堆，所以存入的时候要把距离取负，或者自定义比较器。

3.2 邻接表的两种写法

邻接表有两种常见的实现方式：vector数组和链式前向星。

vector数组的写法更直观，适合大多数场景：

vector<pair<int, 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的好处是相加不会溢出 vector<pair<int, 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_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, 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}，取出时再取负。两种方式都可以，我习惯用第一种，更直观。

提示：如果你用的是Python，heapq本身就是小根堆，直接存(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往回走） vector<int> 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轮松弛，每一轮代表经过一条边。或者用分层图的思路，把每个点拆成k+1个状态，分别表示经过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 超时类问题

问题一：用了朴素Dijkstra，n=10⁵直接超时。

朴素Dijkstra的时间复杂度是O(n²)，n=10⁵的时候就是10¹⁰次操作，肯定超时。换成堆优化版本，复杂度降到O(m log n)，10⁵级别的数据轻松跑过。

问题二：用了SPFA被卡超时。

SPFA的最坏时间复杂度是O(nm)，出题人如果故意构造网格图或者菊花图，很容易把SPFA卡到最坏情况。解决办法：如果边权非负，换堆优化Dijkstra；如果确实有负权边，考虑用Bellman-Ford加队列优化，或者用Johnson算法（先跑一次Bellman-Ford处理负权，再用Dijkstra）。

问题三：优先队列中压入了太多重复元素，导致内存超限。

每个点每次距离被更新都会压入一次，最坏情况下队列中可能有m个元素。对于m=10⁶的题目，队列可能占用较大内存。优化方法：加visited数组，出队时如果已经访问过就跳过；或者用配对堆、斐波那契堆等更高级的数据结构（但一般竞赛中不需要）。

5.3 常见问题速查表

5.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 从这道题能学到什么

“追债之旅”这道题表面上是一道模板题，但它背后的知识体系非常庞大。通过这道题，你应该掌握：

1. 单源最短路的四种核心算法及其适用条件；
2. 堆优化Dijkstra的完整实现和三个关键细节；
3. 多终点、路径输出、负权边等常见变体的处理方式；
4. 常见错误的排查思路和避坑技巧。

这些知识点不仅在竞赛中有用，在面试和实际工程中也是基本功。我个人的建议是：把堆优化Dijkstra的模板背熟，做到不看参考就能写出来；然后理解Bellman-Ford和SPFA的原理，知道什么时候该用它们；最后通过刷题积累变体的处理经验。

我在实际刷题中的体会是，最短路问题的难点从来不是算法本身，而是建模——如何把题目描述转化为图论模型。这需要大量的练习和总结。每做完一道题，花几分钟想一想：这道题的核心考点是什么？如果条件变了该怎么处理？有没有更优的解法？这样积累下来，遇到新题的时候就能快速找到思路。

最后分享一个小技巧：如果你在比赛中遇到最短路问题，但不确定该用哪个算法，可以先看一眼数据范围。n≤100用Floyd，n≤1000用朴素Dijkstra，n≤10⁵用堆优化Dijkstra，有负权边用SPFA或Bellman-Ford。这个经验法则能帮你在短时间内做出正确的选择。