算法常见题型之最短路进阶：多源最短路

算法常见题型之最短路进阶多源最短路例题https://ac.nowcoder.com/acm/contest/132303/H一、题目大意提炼给定一张包含nnn个点、mmm条边的无向正权连通图以及kkk个指定的关键点。要求从这kkk个关键点中选出两个不同的点作为起点和终点求所有可选路径中的最小花费即关键点两两之间最短路径长度的最小值。二、基础回顾单源最短路 Dijkstra 模板适用场景与复杂度Dijkstra 算法用于求解正权图中单一起点到所有节点的最短路径堆优化版本的时间复杂度为 O(mlogn)是处理十万级规模图论问题的标准算法。核心思路初始化距离数组dist为无穷大起点距离设为 0使用小顶堆优先队列维护「当前距离 节点编号」每次取出距离最小的节点若该节点已确定最短路则跳过否则标记为已确定并用该节点松弛所有邻接边重复直到队列为空。标准模板代码#includebits/stdc.h#definepiipairint,int#defineintlonglongusingnamespacestd;constintN1e59,inf1e18;vectorvectorpiig;// 邻接表g[u] 存储 {邻接点v, 边权w}vectorintdist;vectorboolst;voiddijkstra(ints,intn){dist.assign(n1,inf);// 初始化st.assign(n1,false);// 初始化priority_queuepii,vectorpii,greaterpiiq;// 小顶堆dist[s]0;q.push({0,s});while(!q.empty()){auto[d,u]q.top();q.pop();if(st[u])continue;st[u]true;for(auto[v,w]:g[u]){if(dist[v]dw){dist[v]dw;q.push({dist[v],v});}}}}三、常规多源最短路虚拟源点法问题定义多源最短路给定多个源点求每个节点到距离它最近的源点的最短路径长度。经典解法构造一个虚拟源点 S从 S 向每一个源点连接一条权值为 0 的边。此时问题转化为求 S 到所有点的单源最短路仅需跑一次 Dijkstra 即可得到所有点到最近源点的距离时间复杂度仍为 O(mlogn)与单次单源最短路一致。局限性虚拟源点法只能得到「每个点到最近源点的距离」但无法直接求出「任意两个源点之间最短路的最小值」——这正是本题的核心求解目标。四、本题核心解法多源扩展 跨源边统计核心结论对于任意两个不同的源点sss和ttt它们的最短路径上必然存在至少一条边(u,v,w)(u, v, w)(u,v,w)满足uuu的最近源点是sssvvv的最近源点是ttt此时sss到ttt的最短路径长度等于d[u] w d[v]其中d[u]是uuu到最近源点的距离d[v]是vvv到最近源点的距离。因此所有源点对之间的最短路径的最小值就等于所有满足“两端点归属源点不同”的边对应的d[u]wd[v]的最小值。算法步骤初始化距离数组d设为无穷大归属源点数组src设为 -1表示无归属多源入队将所有kkk个关键点加入优先队列设置d[x] 0src[x] x自身为自身的源点Dijkstra 扩展按标准 Dijkstra 流程扩展节点同时维护每个节点的归属源点更新答案在遍历邻边时若边的两个端点都有归属源点且归属不同则用d[u] w d[v]更新全局最小值输出结果最终全局最小值即为答案。五、正解代码#includebits/stdc.h#definepiipairint,int#defineintlonglong// 开long long防止路径长度爆intusingnamespacestd;constintN1e59,inf1e18;intt,n,m,k,ans,x;signedmain(){cint;while(t--){cinnm;vectorvectorpiig(n1);while(m--){inta,b,c;cinabc;g[a].push_back({b,c});g[b].push_back({a,c});// 无向边双向加边}cink;priority_queuepii,vectorpii,greaterq;// 小顶堆vectorintsrc(n1,-1),d(n1,inf);// 初始化vectorboolst(n1);ansinf9;for(inti0;ik;i){cinx;d[x]0;// 源点到自身距离为0src[x]x;// 源点的归属是自己q.push({0,x});// 所有源点同时入队}while(q.size()){auto[dd,id]q.top();q.pop();if(st[id])continue;st[id]1;// 标记该节点最短路已确定for(auto[j,w]:g[id]){// 跨源边两端归属源点不同更新答案if(src[j]!-1src[id]!-1src[j]!src[id])ansmin(ans,wd[id]d[j]);// 标准松弛操作if(d[j]d[id]w){src[j]src[id];// 继承归属源点d[j]d[id]w;q.push({d[j],j});}}}coutans\n;}return0;}六、样例模拟以题目样例为例关键点1、3、5边1-2(1), 2-3(3), 3-1(3), 2-5(1), 2-4(2), 4-3(1)初始d[1]d[3]d[5]0分别入队弹出距离0的节点5扩展邻接点2d[2]更新为1src[2]5入队弹出距离0的节点1扩展邻接点2此时src[1]1src[2]5两者不同计算0 1 1 2ans更新为 2后续扩展其他节点不会得到比 2 更小的跨源路径最终答案为 2与样例输出一致。七、时间复杂度验证时间复杂度无论是单源还是多源总时间复杂度均为 O(mlogn)完全可以通过 n,m1e5 的数据规模。