Zhi*_*ang 5 algorithm optimization computer-science dijkstra shortest-path
我在有向加权图中遇到最短路径问题。我知道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 中至少一个顶点的最小权重树。
该问题称为一般 Steiner 树，是 NP 难问题。因此，您可能希望最好的是指数时间算法或某种近似（想到整个图的最小生成树，也许在删除一些不需要的子树之后）。
有一个简单的 DP 解决方案，工作时间复杂度为 O(2^n * (n + m))：令 f(S) 为图中跨越 S 中所有节点的最小树的成本。可以证明：存在这样一棵树 T，对于某些x ， T \ {x} 的权重为 f(S \ {x}) ，因此可以在 O(n + m) 内完成转换。