我在有向加权图中有最短路径的问题。我知道Dijkstra BFS DFS。然而，我有a set of vertices S作为起点和a set of vertices E to end。S和E不重叠。那么我怎样才能找到权值最小的边的集合呢?边集不必包括S中的所有顶点，但必须包含reach all vertices in E。我应该从Dijkstra开始对{Si, Ei}的所有排列进行优化吗?还是我遗漏了任何我应该知道的重要算法?或者我想太多了....
如果我理解正确的话，你想要在图中找到包含E的所有顶点和s的至少一个顶点的最小权值树
这个问题被称为一般斯坦纳树，它是np困难的。因此，你可能希望得到的最好结果是一个指数时间算法或某种近似(想到整个图的最小生成树，可能在删除一些不需要的子树之后)。
有一个简单的DP解在O(2^n * (n + m))内有效:设f(S)为图中横跨S中所有节点的最小树的代价。可以证明存在这样一棵树T，使得T {x}的权值为f(S {x})对于某些x，因此转换可以在O(n + m)内完成。