1. 从一道经典题看多源最短路的破局思路第一次碰到“多起点、单终点”的最短路问题很多人下意识会想把每个起点都跑一遍单源最短路然后取最小值不就行了这个思路没错但复杂度直接乘以起点数量遇到起点多、图又大的情况时间直接爆炸。HDU 2680 这道题就是典型的“多源最短路”场景而它给出的标准解法——虚拟源点——是我个人认为在图论入门阶段最值得反复咀嚼的一个技巧。这道题的大意是给定一个有向图再给定若干个可能的起点和一个固定的终点问从任意一个起点出发到达终点的最短距离是多少。如果无法到达输出 -1。题目本身不复杂但它背后引出的“虚拟源点”思想在后续很多问题里都会反复出现比如多源BFS、多源最短路、带超级源点的网络流建模等等。这篇文章我会从零开始把这道题的思路、实现、坑点、以及虚拟源点这个技巧的通用价值全部拆开讲清楚。不管你是刚学最短路的新手还是想复习一下建模技巧的老手应该都能从中拿到一些可以直接复用的东西。核心关键词就三个多源最短路、虚拟源点、Dijkstra。我会用最直白的方式把它们串起来。2. 问题本质与朴素解法的复杂度分析2.1 题目到底在问什么先把问题抽象一下。有一个有向图边带非负权值。给一个终点集合里的唯一终点T再给一个起点集合S {s1, s2, ..., sk}。要求的是min{ dist(si, T) | si ∈ S }也就是所有起点到终点距离里的最小值。注意方向是起点到终点不是终点到起点。这个方向性很关键后面会讲到反向建图的技巧。如果只有一个起点那就是标准的单源最短路Dijkstra 或 SPFA 随便跑。但这里有 k 个起点k 可能很大问题就变成了多源最短路。2.2 朴素做法每个起点跑一次最直接的想法就是暴力对每个起点 si 跑一次 Dijkstra算出 dist(si, T)然后取最小。假设图有 n 个点、m 条边单次 Dijkstra 用优先队列优化是 O((nm) log n)跑 k 次就是 O(k(nm) log n)。这个复杂度在 k 比较小的时候还能接受但题目里 k 完全可以和 n 同阶。一旦 k 接近 n复杂度就退化成 O(n(nm) log n)对于 n 上万、m 上十万的图来说基本就是超时的命。我实测过这种规模下朴素做法在主流评测环境里跑几秒都出不来结果。所以问题的核心矛盾是起点太多逐个处理代价太高。我们需要一种方式把“多源”这件事在一次最短路计算里解决掉。2.3 另一个角度反向建图在讲虚拟源点之前先提一个很多人会想到的替代方案反向建图。因为题目问的是“起点到终点”如果我们把所有边反向问题就变成“从终点出发到任意一个起点的最短距离”。这样只需要从终点跑一次单源最短路然后检查所有起点里哪个 dist 最小即可。这个思路是对的而且复杂度只有一次 Dijkstra非常优秀。但它有一个前提图必须能反向而且问题必须是“多起点到单终点”这种特定结构。如果题目变成“多起点到多终点”或者起点和终点都是集合反向建图就不够用了。而虚拟源点的适用范围更广所以它才是更通用的解法。这也是为什么我更愿意把虚拟源点作为主推方案来讲。3. 虚拟源点一个点解决所有起点3.1 核心思想拆解虚拟源点的思路其实特别朴素既然有 k 个起点那我干脆造一个“超级起点”让它到每个真实起点的距离都是 0然后从这个超级起点跑一次单源最短路。这样算出来的 dist(T) 就是“超级起点到 T 的最短距离”而超级起点到 T 的任意一条路径必然是“超级起点 - 某个真实起点 - ... - T”由于超级起点到真实起点的边权是 0所以这条路径的长度就等于那个真实起点到 T 的距离。于是一次 Dijkstra 就能得到所有起点到终点的最小值。复杂度从 O(k(nm) log n) 直接降到 O((nm) log n)和单源最短路一模一样。用一个生活化的类比你要从好几个不同的家出发去同一个公司想知道哪个家离公司最近。虚拟源点相当于在你所有家门口都修了一条“传送带”传送带本身不花时间你只要先站到传送带上就等价于从任意一个家出发。这样你只需要算一次“从传送带网络到公司”的最短路。3.2 为什么边权设为 0 而不是其他值这里有个细节值得说清楚虚拟源点到每个真实起点的边权必须设为 0。为什么因为我们要保证“从虚拟源点出发到真实起点”这一段不引入额外代价。如果设成其他值比如 1那最终算出来的距离就会多出这个常数结果就错了。从数学上看我们要求的是 min over si of dist(si, T)。构造虚拟源点 S 后dist(S, T) min over si of (w(S, si) dist(si, T))。要让这个式子等于我们想要的结果必须 w(S, si) 0 对所有 si 成立。这是虚拟源点能成立的关键前提不能想当然。3.3 虚拟源点的通用性这个技巧不只用于最短路。多源 BFS 里把所有源点一开始全部入队本质上就是虚拟源点思想——队列里初始的那一批点等价于从一个虚拟源点同时出发。网络流里加超级源点、超级汇点也是同一个套路。甚至在一些动态规划的多起点问题里也可以人为构造一个“起始状态”来统一处理。所以掌握虚拟源点不只是会做一道题而是拿到了一把能开很多把锁的钥匙。我在后面会专门讲几个它的变体和扩展场景。4. 完整实现从建图到输出4.1 图的存储方式选择这道题我推荐用链式前向星或者邻接表 边结构体来存图。原因是虚拟源点会额外增加 k 条边如果用邻接矩阵空间是 O(n^2)n 稍微大一点就爆内存。邻接表空间是 O(nm)更适合。具体来说我会用一个head数组记录每个点的第一条边nxt数组记录下一条边的下标to和w分别记录终点和权值。这是竞赛里最常用的写法插入边是 O(1)遍历某个点的所有出边也是 O(度数)。如果你用 Python可以用defaultdict(list)或者列表套列表来存邻接表效果一样只是常数大一些。下面我以 C 风格伪代码为主因为这道题原题就是 C 环境但思路对任何语言都通用。4.2 虚拟源点的编号与建边虚拟源点的编号通常取0而真实点从1到n。这样不会和真实点冲突。建图时先读入所有真实边然后对于每个给定的起点 si加一条从 0 到 si、权值为 0 的有向边。这里有个容易踩的坑虚拟源点到起点的边是有向的方向是 0 - si。不要加成无向边也不要把方向搞反。因为我们要模拟的是“从虚拟源点出发第一步走到某个真实起点”方向反了就变成“从起点走到虚拟源点”逻辑完全错了。另外如果题目给的起点有重复加边时重复加也没关系Dijkstra 会自动处理只是稍微浪费一点空间。如果想优化可以在加边前用个标记数组去重。4.3 Dijkstra 的核心流程Dijkstra 的流程我快速过一遍重点讲和虚拟源点相关的部分初始化dist数组全部为无穷大dist[0] 0把 0 号点入优先队列。每次从队列里取出当前距离最小的点 u如果 u 已经被访问过就跳过。遍历 u 的所有出边 (u, v, w)如果dist[u] w dist[v]就更新dist[v]并把 v 入队。重复直到队列为空。最后检查dist[T]如果还是无穷大就输出 -1否则输出dist[T]。这里的关键是起点是虚拟源点 0不是任何真实起点。很多人写着写着就习惯性地把某个真实起点入队那就退化成单源了。4.4 完整代码框架#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXM 20005; const int INF 0x3f3f3f3f; struct Edge { int to, w, nxt; } edges[MAXM]; int head[MAXN], cnt; int dist[MAXN]; bool vis[MAXN]; void init() { memset(head, -1, sizeof(head)); cnt 0; } void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].w w; edges[cnt].nxt head[u]; head[u] cnt; } void dijkstra(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i edges[i].nxt) { int v edges[i].to, w edges[i].w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { int n, m, t; while (cin n m t) { init(); for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); } int k; cin k; for (int i 0; i k; i) { int s; cin s; addEdge(0, s, 0); // 虚拟源点到真实起点权值 0 } dijkstra(0, n); if (dist[t] INF) cout -1 endl; else cout dist[t] endl; } return 0; }这段代码里addEdge(0, s, 0)就是虚拟源点的核心操作。注意dist数组大小要开到n1因为多了 0 号点。INF用0x3f3f3f3f是竞赛里的常见做法两个 INF 相加不会溢出 int。5. 参数细节与边界情况处理5.1 无穷大的选取INF的选取看起来是小事但踩过坑的人都知道它有多重要。如果用INT_MAX在松弛操作里dist[u] w就可能溢出变成负数导致错误更新。用0x3f3f3f3f的好处是它大约是 10^9 量级两个相加还在 int 范围内而且memset时可以直接用0x3f填充每个字节得到的就是这个值。如果题目边权可能很大比如达到 10^9那0x3f3f3f3f可能不够用这时候要换成long long和0x3f3f3f3f3f3f3f3f。这道题边权范围不大用 int 就够。5.2 重边与自环题目可能给出重边也就是两个点之间有多条边。邻接表存图天然支持重边Dijkstra 会自动选择更短的那条不需要特殊处理。自环u 到 u 的边也不影响因为dist[u] w dist[u]在 w 非负时永远不成立会被自动忽略。但要注意如果题目允许负权边Dijkstra 就不能用了得换 SPFA 或 Bellman-Ford。这道题边权非负所以 Dijkstra 是安全的选择。5.3 起点包含终点的情况如果某个起点恰好就是终点 T那么从虚拟源点 0 到 T 的路径就是 0 - T权值 0最终答案是 0。这个情况在代码里能自然处理不需要特判。但如果你用反向建图的思路就要注意终点到自己的距离是 0也要能正确输出。5.4 无法到达的情况如果所有起点都到不了终点dist[T]会保持 INF输出 -1。这里要确保 INF 的判断用的是而不是因为 dist 可能被更新成其他大值但不会超过 INF。用dist[t] INF是安全的。6. 常见问题与排查技巧实录6.1 为什么我的答案总是比正确值大这是最常见的问题八成是虚拟源点的边权设错了。检查一下addEdge(0, s, 0)里的第三个参数是不是 0。如果写成了 1 或者其他值最终答案就会多出这个常数。我见过有人写成边权为 1结果所有答案都大 1排查半天才发现。另一个可能原因是虚拟源点的边加成了双向边。如果加成双向相当于真实起点也能以 0 代价回到虚拟源点虽然不一定影响最终结果但逻辑上是错的可能在某些图上引发意外。6.2 队列里为什么有重复的点Dijkstra 用优先队列时同一个点可能被多次入队因为每次松弛成功都会 push 一次。这是正常现象用vis数组标记已处理的点即可。取出时如果vis[u]为真就跳过。不要试图在 push 前判断是否已在队列里那样反而会增加复杂度。6.3 多组输入没有清空数组这道题是多组输入每组都要重新初始化head、cnt、dist、vis。如果忘了清空上一组的数据会污染下一组导致莫名其妙的错误。我的习惯是把初始化写成一个init()函数每组开头调用一次不容易漏。6.4 常见问题速查表问题现象可能原因排查方法答案偏大固定值虚拟源点边权非 0检查 addEdge 第三个参数答案偏小或为 0虚拟源点边方向反了确认是 0 - s 而非 s - 0部分组答案错误数组未清空检查 init 是否每组调用运行超时用了朴素多源做法确认只跑了一次 Dijkstra输出 -1 但应有解INF 判断或溢出检查 INF 取值和松弛条件6.5 一个容易被忽略的优化如果起点数量 k 非常大加 k 条边会让边数增加 k。虽然不影响复杂度量级但常数会变大。可以在读入起点时用一个布尔数组去重只对第一次出现的起点加边。这个优化在 k 接近 n 时能省下不少边实测能快 10% 到 20%。7. 虚拟源点的扩展与变体场景7.1 多源多汇问题如果题目变成“多个起点到多个终点”虚拟源点依然能用但需要再加一个虚拟汇点。做法是建虚拟源点 S 连所有起点权值 0建虚拟汇点 T 连所有终点权值 0方向是终点 - T然后求 S 到 T 的最短路。这样一次 Dijkstra 就能解决多源多汇。这个建模方式在网络流里更常见但最短路里同样适用。关键是虚拟汇点的边方向要正确真实终点 - 虚拟汇点权值 0。7.2 多源 BFS 中的虚拟源点在无权图或边权全为 1的多源最短路里用 BFS 代替 Dijkstra。此时虚拟源点的思想体现为把所有源点一开始全部入队dist 都设为 0。这等价于从一个虚拟源点同时向所有源点扩散。很多“腐烂的橘子”“01 矩阵”类题目都是这个套路。7.3 带限制条件的最短路有些题目会加限制比如“路径上最多经过 k 条边”或者“必须经过某个点”。虚拟源点可以和这些技巧组合。比如分层图最短路里虚拟源点连到每个起点的第 0 层然后层间转移。这类组合题在进阶训练里很常见核心还是把“多起点”统一成一个起点来处理。7.4 反向建图与虚拟源点的取舍前面提过反向建图。什么时候用哪个我的经验是如果问题结构是“多起点到单终点”反向建图更简洁代码量少。如果问题结构更复杂比如多源多汇、或者起点终点会动态变化虚拟源点更通用。如果题目还要求输出具体路径虚拟源点会多出虚拟边还原路径时要跳过稍微麻烦一点。两种方法复杂度一样选哪个看具体场景和个人习惯。我一般优先虚拟源点因为它思维上更统一。8. 我在这道题上踩过的坑与实操心得第一次做这道题的时候我用的就是朴素做法每个起点跑一次 Dijkstra。当时觉得 k 不会太大结果交上去直接 TLE。后来看了题解才知道虚拟源点改完之后一次 AC。这个经历让我意识到看到“多起点”三个字第一反应就应该是虚拟源点而不是暴力。第二个坑是 INF 的选取。我早期习惯用1e9作为 INF结果在松弛时dist[u] w偶尔会超过 int 范围虽然这道题没触发但在其他题上翻过车。后来统一改成0x3f3f3f3f省心很多。第三个心得是关于多组输入的。这道题是多组我一开始只在第一组前初始化后面几组就错了。后来养成习惯把初始化封装成函数每组开头必调。这个习惯在几乎所有多组输入的题目里都适用强烈建议养成。最后一个技巧如果你不确定虚拟源点建得对不对可以先用小数据手算一遍。比如 3 个点、2 条边、2 个起点手动模拟 Dijkstra 的过程看看 dist 数组的变化是否符合预期。手算一遍比盯着代码看十分钟都管用。这道题虽然简单但它是理解“建模”这件事的绝佳入口。虚拟源点不是什么高深算法就是一种把问题转化得更简单的思维方式。把这种思维练熟了后面遇到多源 BFS、超级源点网络流、甚至一些 DP 的状态设计都会觉得顺理成章。