多源多目标最短路径问题

Question

我试图找出一种最佳方法来获得从所有源节点到任何一个目标节点的最短路径，从而导致加权图中的权重最小。所有节点要么是源节点，要么是目标节点。因此，我们有一个图，其中 A、B、C 作为源节点，D、E、F 作为目标节点。A、B、C 必须找到到达任意一个恰好具有最短路径的目标节点的最短路径。

简单的解决方案是使用 Dijkstra 算法或类似的算法，首先找到从 A 到 D 的最短路径，然后从 A 到 E 等，然后比较每条最短路径的最终权重，看看哪条实际上是最短的。我想知道是否有更有效的解决方案。

Answer 1

添加一个通向所有源的新节点（使这些新边的权重为 0），并从新节点运行 Dijkstra's。