求带权图中从顶点s到自身且经子集U的最轻路径高效算法

核心思路 #

由于图中所有边权重均为正实数，我们可以基于Dijkstra算法，通过三次最短路径计算、拆分路径结构来高效求解目标问题。

具体步骤 #

1. 计算起点s到所有顶点的直接最短路径 #

运行标准Dijkstra算法，以s为起点，得到数组dist_s，其中dist_s[v]代表从s到顶点v的最短路径权重（无强制经过U的要求）。

2. 计算所有顶点到U中任意节点的最短路径 #

• 先构建原图的反向图：将每条边(u, v)反转方向为(v, u)，权重保持不变。
• 在反向图上执行多源Dijkstra算法：把U中所有顶点作为初始起点（初始时这些顶点的距离设为0，其余为无穷大），得到数组dist_to_U，其中dist_to_U[v]代表从v到U中任意顶点的最短路径权重。

3. 推导每个顶点的目标路径权重 #

对于每个顶点v∈V，我们要求的是「从s出发到v，且至少经过U中一个顶点」的最短路径。这条路径必然可以拆分为：s → ... → u → ... → v（其中u∈U）。因此：

• 目标权重target_dist[v] = min{ dist_s[u] + dist_to_U[v] | u ∈ U }
• 特殊情况：若v本身属于U，target_dist[v]可直接取dist_s[v]（因为路径s→v已经满足经过U的要求）

效率说明 #

• 单源Dijkstra（二叉堆实现）的时间复杂度为O(M log N)，三次运行的总复杂度为O(M log N)，属于正权图下的高效解法。
• 多源Dijkstra无需额外添加虚拟节点，直接初始化优先队列即可，避免了冗余计算。

补充：若问题为s到s的回路（经过U） #

如果原问题实际需求是「从s出发回到s，且至少经过U中一个顶点」的最短回路权重，只需计算：
min{ dist_s[u] + dist_to_U[s] | u ∈ U }
即s到u的最短路径加上u回到s的最短路径，取所有u∈U中的最小值。

内容的提问来源于stack exchange，提问作者Ravid s