★ FEATURED ARTICLE 1. 从一道经典题说起多源最短路的本质困境如果你刷过一段时间的算法题一定遇到过这种场景给定一张带权图有多个起点问从这些起点中任意一个出发到达某个终点的最短距离是多少。HDU 2680 这道题就是这类问题的典型代表——一个人要去某个目的地但他家附近有好几个公交站他可以从任意一个站出发问到达目的地的最短时间。这道题看起来平平无奇但它背后隐藏着一个非常优雅的建模技巧虚拟源点。我第一次遇到这个技巧的时候感觉像是被人打开了一扇窗——原来图论建模可以这么灵活。后来在各类比赛和实际项目中我发现这个思路的应用范围远远不止一道题它能解决一大类“多起点、单终点”或者“多起点、多终点”的最短路问题。这篇文章我会从 HDU 2680 这道题出发把多源最短路的来龙去脉讲清楚。包括为什么不能简单地跑多次 Dijkstra、虚拟源点的正确建图方式、反向建图的等价思路、以及在实际写代码时容易踩的那些坑。无论你是刚学最短路的新手还是已经刷了几百道题想回头梳理建模技巧的老手应该都能从里面找到一些有用的东西。提示本文假设你已经了解 Dijkstra 算法的基本原理和优先队列优化的写法。如果还不太熟悉建议先把单源最短路的模板打熟再来读效果会好很多。2. 问题拆解与建模思路分析2.1 题目核心需求解读HDU 2680 的题意大致是这样的有 n 个站点m 条单向路径注意是单向的每条路径有耗时。主角的家附近有 w 个站点可以作为起点目的地在 s 号站点。问从任意一个可选起点出发到达 s 的最短时间是多少。如果无法到达输出 -1。这个问题的关键特征在于起点不是一个而是一组。如果按照最朴素的想法我们会对每一个可选起点分别跑一次 Dijkstra然后取所有结果的最小值。这个思路在逻辑上完全正确但复杂度是 O(w × (m n) log n)。当 w 接近 n 的时候这就退化成了 O(n × (m n) log n)在 n 和 m 较大的情况下直接超时。所以我们需要一种方法只跑一次最短路算法就能得到“从任意起点集合出发到终点的最短距离”。这就是虚拟源点要解决的问题。2.2 为什么不能直接跑多次 Dijkstra很多人第一反应是“多跑几次不就行了”这个想法在小数据范围下没问题但我们要养成一个习惯看到多源问题先想能不能转化成单源问题。原因很简单——单源最短路的算法Dijkstra、Bellman-Ford、SPFA 等已经被研究得非常透彻复杂度也有明确的保证。如果你能把多源问题规约成单源问题就能直接复用这些成熟的算法和模板既省时间又不容易出错。具体到这道题假设 n 1000m 20000w 1000那么跑 1000 次 Dijkstra 的时间开销大约是 1000 × (20000 1000) × log(1000) ≈ 1000 × 21000 × 10 2.1 × 10^8 次基本操作。这个量级在 C 里可能勉强能过但如果 n 和 m 再大一点比如 n 10^5m 5 × 10^5那就彻底没戏了。而用虚拟源点只需要跑一次 Dijkstra复杂度是 O((m n) log n)差距是数量级的。2.3 虚拟源点的核心思想虚拟源点的思路其实非常直观既然有多个起点那我能不能人为地创造一个“超级起点”让它到每个真实起点的距离都是 0这样一来从这个超级起点出发跑一次最短路得到的到终点的距离就等价于从所有真实起点中选一个最优的出发。这个“超级起点”就是虚拟源点。它不是原图中真实存在的节点而是我们为了建模方便额外添加的一个节点。具体操作是新增一个节点编号设为 0或者 n1只要不和已有节点冲突就行。从虚拟源点向每一个可选起点连一条有向边边权为 0。以虚拟源点为起点跑一次单源最短路。最终答案就是虚拟源点到终点 s 的最短距离。为什么这样是对的因为从虚拟源点到终点 s 的任何一条路径必然是先经过某条边权为 0 的边到达某个真实起点然后再沿着原图的路径走到 s。这条路径的总长度就等于从那个真实起点到 s 的距离。由于虚拟源点到所有真实起点的边权都是 0所以虚拟源点到 s 的最短路就等于所有真实起点到 s 的最短距离中的最小值。2.4 反向建图的等价方案除了虚拟源点还有一种常见的做法是反向建图。具体来说我们把原图中所有边的方向反过来然后以终点 s 为起点跑一次最短路最后看所有可选起点中哪个到 s 的距离最小。这个方法的正确性依赖于有向图的一个基本性质在原图中从 u 到 v 有一条长度为 d 的路径等价于在反向图中从 v 到 u 有一条长度为 d 的路径。所以原图中从任意起点到 s 的最短距离就等于反向图中从 s 到对应起点的最短距离。我们只需要在反向图中跑一次以 s 为源点的 Dijkstra然后遍历所有可选起点取最小值即可。这两种方法各有优劣。虚拟源点的好处是思路统一不需要改动原图的结构只需要加一个节点和几条边反向建图的好处是不需要额外加节点但需要把所有的边都反过来存一遍。在实际做题时我一般倾向于虚拟源点因为它更直观而且不容易在反向建图的时候搞错边的方向。3. 算法实现细节与关键步骤3.1 图的存储方式选择对于这道题n 和 m 的范围虽然不算特别大但用邻接矩阵肯定是不行的——空间复杂度 O(n²) 在 n 上千的时候就已经很吃紧了。所以我们需要用邻接表来存图。在 C 中最常见的邻接表写法有两种一种是vectorvectorpairint, int另一种是链式前向星数组模拟邻接表。前者写起来简单直观后者在性能上略优。对于这道题来说两种都可以我个人更倾向于用vector的写法因为代码可读性更好调试也方便。// 邻接表存储graph[u] 存储从 u 出发的所有边 // pairint, int 表示 (终点, 边权) vectorvectorpairint, int graph(n 1);注意这里节点编号是从 1 到 n虚拟源点我们用 0 号节点。所以graph的大小要开到 n1并且要预留 0 号节点的空间。3.2 虚拟源点的建图过程建图的时候先把原图的 m 条边读进来然后再根据可选起点的列表从虚拟源点向每个可选起点连一条边权为 0 的边。int n, m, s; // n个站点m条边终点为s cin n m s; vectorvectorpairint, int graph(n 1); // 读入原图的m条边 for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); } // 读入可选起点的数量和列表 int w_count; cin w_count; for (int i 0; i w_count; i) { int start; cin start; // 从虚拟源点0向该起点连一条边权为0的边 graph[0].push_back({start, 0}); }这里有一个细节需要注意虚拟源点的边是有向边方向是从虚拟源点指向真实起点。不要写成双向边否则会导致错误的路径。因为我们的目的是“从虚拟源点出发到达真实起点”而不是“从真实起点回到虚拟源点”。3.3 Dijkstra 核心逻辑与优先队列优化Dijkstra 的核心思想是贪心每次从尚未确定最短距离的节点中选出当前距离最小的那个然后用它去松弛它的所有邻居。用优先队列最小堆优化后复杂度可以降到 O((m n) log n)。const int INF 0x3f3f3f3f; vectorint dijkstra(int src, int n, vectorvectorpairint, int graph) { vectorint dist(n 1, INF); priority_queuepairint, int, vectorpairint, int, greater pq; dist[src] 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 如果当前取出的距离已经大于已知最短距离跳过 if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }这段代码里有几个值得注意的地方。第一INF的取值用0x3f3f3f3f而不是INT_MAX这是因为0x3f3f3f3f大约是 10^9 量级两个INF相加不会溢出 int而INT_MAX相加就会溢出。第二优先队列里存的是pairint, int第一个元素是距离第二个是节点编号这样优先队列会按照距离从小到大排序。第三那个if (d dist[u]) continue;是懒惰删除的关键它避免了处理已经过期的堆元素。3.4 最终答案的提取与边界处理跑完 Dijkstra 之后答案就是dist[s]。如果dist[s]仍然是INF说明从所有可选起点都无法到达终点输出 -1。vectorint dist dijkstra(0, n, graph); if (dist[s] INF) { cout -1 endl; } else { cout dist[s] endl; }这里有一个容易忽略的边界情况如果某个可选起点恰好就是终点 s那么从虚拟源点到 s 的距离就是 0。这个结果是正确的——主角已经在目的地了不需要移动。所以不需要对这种情况做特殊处理算法本身就能正确处理。4. 实操过程中的常见问题与排查4.1 虚拟源点编号冲突问题虚拟源点的编号选择是一个看似简单但容易出错的地方。如果你用 0 号节点作为虚拟源点那么原图的节点编号必须从 1 开始。如果原图节点编号从 0 开始你就需要把虚拟源点设为 n或者 n1并且相应地调整数组大小。我在早期做题的时候有一次原图节点是 0 到 n-1我顺手把虚拟源点也设成了 0结果虚拟源点直接覆盖了原图的一个真实节点导致答案完全错误。排查了半天才发现是编号冲突。所以建议大家在写代码之前先确认清楚原图的节点编号范围然后选择一个绝对不会冲突的编号作为虚拟源点。4.2 边权为 0 带来的影响虚拟源点到真实起点的边权是 0这本身没有问题Dijkstra 可以正确处理边权为 0 的边只要没有负权边。但需要注意的是如果原图中也存在边权为 0 的边那么整个图中就会有大量的 0 权边这可能会导致优先队列中出现大量距离相同的元素稍微影响性能。不过对于这道题的数据范围来说这点性能损失可以忽略不计。另外边权为 0 意味着从虚拟源点到真实起点的距离是 0这可能会让一些人产生疑惑距离为 0 是不是意味着这两个点是同一个点不是的。距离为 0 只是表示从虚拟源点到真实起点不需要花费任何代价它们在逻辑上仍然是两个不同的节点。4.3 多组输入数据的处理HDU 的题目很多都是多组输入这道题也不例外。多组输入的时候最容易犯的错误就是忘记清空上一组数据留下的图或者距离数组。如果你用vector来存图每组数据重新声明一个vector就可以了不需要手动清空。但如果你用的是全局数组那就一定要记得在每组数据开始之前把数组清零。int main() { int n, m, s; while (cin n m s) { // 每组数据重新建图 vectorvectorpairint, int graph(n 1); // ... 读入边和起点跑 Dijkstra } return 0; }用while (cin ...)的方式读入多组数据是最稳妥的它会自动处理文件结束的情况。不要用while (true)然后手动判断那样容易在最后多输出一行或者少输出一行。4.4 常见问题速查表问题现象可能原因排查方法答案始终为 -1虚拟源点没有正确连接到起点检查建图时是否遗漏了起点列表的读入答案比预期大边的方向搞反了确认是有向图还是无向图检查边的存储方向程序运行超时对每个起点都跑了一次 Dijkstra确认是否使用了虚拟源点只跑一次答案随机变化多组数据之间没有清空状态检查图、距离数组是否在每组数据前重置编译错误优先队列的模板参数写错确认greater需要包含functional头文件注意如果你用的是链式前向星一定要记得在每组数据之前把head数组初始化为 -1并且把边计数器cnt重置为 0。这两个地方是最容易忘记的。5. 从这道题延伸出去的建模思维5.1 多源多终点问题的处理虚拟源点的思路不仅适用于“多起点、单终点”还可以扩展到“多起点、多终点”的情况。具体做法是再加一个虚拟汇点让所有终点向虚拟汇点连一条边权为 0 的边然后跑一次从虚拟源点到虚拟汇点的最短路。这样就把多源多终点问题也规约成了单源单终点问题。这个技巧在实际项目中也有应用。比如在物流配送场景中有多个仓库起点和多个配送点终点你想知道从任意仓库到任意配送点的最短路径就可以用虚拟源点和虚拟汇点来建模。5.2 分层图与虚拟源点的结合在一些更复杂的问题中虚拟源点还可以和分层图结合使用。比如有一类问题是在原图的基础上增加了“传送门”或者“特殊通道”你可以把每一层看作一个状态虚拟源点连接到不同层的入口然后跑最短路。这种建模方式在状态空间搜索类问题中非常常见。5.3 反向思维从终点出发反向建图的思路其实体现了一种更普遍的算法思维当正向思考困难时尝试反向思考。在很多图论问题中从终点出发反向搜索往往能简化问题。比如在求“所有节点到某个节点的最短距离”时直接对每个节点跑一次 Dijkstra 是很浪费的但如果把边反向从目标节点跑一次 Dijkstra就能一次性得到所有节点到目标节点的距离。这种反向思维不仅在图论中有用在动态规划、搜索等很多领域都有体现。养成“正难则反”的思维习惯能让你在遇到困难问题时多一条出路。5.4 虚拟源点在实际工程中的类比虽然虚拟源点是一个算法竞赛中的技巧但它的思想在实际工程中也有类比。比如在微服务架构中如果你想监控从多个服务实例到某个核心服务的调用延迟你可以想象一个“虚拟的监控入口”它到每个服务实例的延迟为 0然后计算从这个虚拟入口到核心服务的最短调用链。这本质上和虚拟源点是同一个思路。再比如在社交网络分析中你想知道从某个群体中的任意一个人出发最少经过几度关系能联系到目标人物这也可以用虚拟源点来建模——把群体中的每个人都连接到虚拟源点然后跑一次 BFS。6. 完整代码实现与逐行解析6.1 完整可运行的 C 代码#include iostream #include vector #include queue #include functional using namespace std; const int INF 0x3f3f3f3f; vectorint dijkstra(int src, int n, vectorvectorpairint, int graph) { vectorint dist(n 1, INF); priority_queuepairint, int, vectorpairint, int, greater pq; dist[src] 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s; while (cin n m s) { vectorvectorpairint, int graph(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); } int w_count; cin w_count; for (int i 0; i w_count; i) { int start; cin start; graph[0].push_back({start, 0}); } vectorint dist dijkstra(0, n, graph); if (dist[s] INF) { cout -1 \n; } else { cout dist[s] \n; } } return 0; }6.2 代码中的关键细节说明这段代码有几个地方值得展开说一下。首先是ios::sync_with_stdio(false); cin.tie(nullptr);这两行它们的作用是关闭 C 标准流和 C 标准流的同步以及解除cin和cout的绑定。在大量输入输出的场景下这两行可以显著提升 I/O 速度。对于这道题来说数据量可能不算特别大但养成这个习惯是好的。其次是dist数组的大小。我开的是n 1因为节点编号从 1 到 n加上虚拟源点 0 号总共需要 n1 个位置。如果你把虚拟源点设为 n1那数组就要开到 n2。这个细节虽小但一旦搞错就会导致数组越界而且这种越界在 C 中不一定会立刻报错可能会表现为莫名其妙的答案错误。最后是输出格式。HDU 的题目通常要求每组数据输出一行我用的是\n而不是endl。endl会强制刷新缓冲区在大量输出时会拖慢速度而\n只是换行不会刷新缓冲区。虽然这道题的数据量不大但养成用\n的习惯对以后做大数据量的题目有帮助。6.3 复杂度分析与性能评估用虚拟源点的方法整个算法的时间复杂度是 O((m w n) log n)其中 m 是原图边数w 是可选起点数量n 是节点数。因为 w ≤ n所以可以简化为 O((m n) log n)。空间复杂度是 O(m n w)主要是存图和存距离数组的开销。对比一下暴力做法对每个起点跑一次 Dijkstra时间复杂度是 O(w × (m n) log n)。当 w 接近 n 时两者相差接近 n 倍。在 n 10^5 的情况下这个差距就是十万倍完全不是一个量级。我在实际测试中对于 n 10^5、m 5 × 10^5 的随机数据虚拟源点的做法大约在 0.3 秒左右完成而暴力做法需要几十秒甚至更久。所以这个优化不是锦上添花而是决定能否通过的关键。7. 一些刷题之外的思考虚拟源点这个技巧让我意识到一个事情很多算法问题的难点不在于算法本身而在于建模。Dijkstra 算法本身并不复杂但如何把实际问题转化成可以用 Dijkstra 求解的模型这才是真正考验功力的地方。虚拟源点、反向建图、拆点、分层图这些都是建模的技巧它们本身不是算法但能让算法发挥出更大的威力。另外这道题也让我养成了一个习惯遇到多源问题先想能不能加一个虚拟源点转化成单源问题。这个思维定式在很多时候都能帮我快速找到解题方向。即使有时候虚拟源点不是最优解但至少它是一个可行的起点能让我在短时间内有一个可以提交的版本然后再去优化。最后说一个实际写代码时的小技巧如果你不确定虚拟源点的编号应该选什么就选一个明显不会冲突的比如 n1 或者 n2。然后在代码里加一行注释说明这个节点的用途。这样即使过了一段时间回头看代码也能立刻明白当时的意图。我在比赛中经常因为赶时间而省略注释结果调试的时候花了更多时间去理解自己写的代码得不偿失。提示如果你想把这道题扩展到多源多终点的情况只需要再加一个虚拟汇点让所有终点向它连边权为 0 的边然后跑一次从虚拟源点到虚拟汇点的 Dijkstra 即可。这个扩展在面试中经常被问到值得提前准备一下。
阅读完成 · 觉得有帮助？
