我在有向加权图中的最短路径遇到问题。我知道Dijkstra，BFS，DFS。但是，我有a set of vertices S作为起点和a set of vertices E to end。 S和E不重叠。那么，如何找到边缘权重总和最小的一组边缘呢？边集不必包含S中的所有顶点，而必须包含reach all vertices in E。我应该从{Si，Ei}的所有排列开始以Dijkstra进行优化，还是错过任何我应该知道的重要算法？甚至我都在想太多...
最佳答案
如果我理解正确，则您想在图中找到权重最小的树，其中包含E的所有顶点和S的至少一个顶点。
这个问题称为general Steiner tree，它是NP难的。因此，您可能希望的最佳选择是指数时间算法或某种近似(可以想到整个图形的minimum spanning tree，也许是在删除了一些不需要的子树之后)。
有一个简单的DP解决方案可以在O(2 ^ n *(n + m))中工作:令f(S)是图中覆盖S中所有节点的最小树的代价。存在这样的树T，使得对于某些x，T\{x}的权重为f(S\{x})，因此可以在O(n + m)中完成转换。
关于algorithm - 多起点和多终点最短路径集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23414719/