多起点和多终点的最短路径集合

Question

我在有向带权图中遇到了最短路径的问题。我知道 Dijkstra、BFS 和 DFS 算法。但是，我有一组起点 S 和一组终点 E。S 和 E 之间没有重叠部分。那么，如何找到边集合的最小边权和？边集合不必包括 S 中的所有顶点，但必须涵盖 E 中的所有顶点。我应该对 {Si，Ei} 的所有排列使用 Dijkstra 算法并进行优化，还是我错过了任何重要算法应该知道的？或者我想太多了...

- ZhijieWang

---

添加两个顶点，一个起点，与S中的所有顶点相连，另一个终点，所有E中的顶点都与之相连。在新图上运行Dijkstra算法。 - user58697

然而，最短路径 (集合) 将会到达终点，但不一定会到达 E 中的所有顶点。 - ZhijieWang

如果从起点到终点的路径是最短的，那么它就是从{S}到{E}的所有路径中最短的。除非我完全误读了问题。 - user58697

假设集合E中有E1和E2。您可以通过E1到达End，完全错过E2。 - ZhijieWang

Answer 1

如果我理解正确，您想在包含E中所有顶点和至少一个来自S的顶点的图中找到最小权重的树。

这个问题被称为通用斯坦纳树，它是NP难问题。因此，您可能最好希望得到一种指数时间算法或某种近似算法（整个图的最小生成树可能会出现在脑海中，也许在删除一些不必要的子树之后）。

有一个简单的DP解决方案，可以在O(2^n * (n + m))内运行：令f(S)为跨越S中所有节点的图中最小树的成本。可以证明存在这样的树T，使得T \ {x}的权重为f(S \ {x})，因此转换可以在O(n + m)内完成。

- Niklas B.

---

@user1505108 好吧，那么问题并不是很明显，但它很难。 - Niklas B.

@user1505108 我添加了一个O(2^n * (n + m))的DP算法，如果有帮助的话。至少它不会在边的数量上呈指数增长。 - Niklas B.