如何最小化最短路径树的总代价

Question

我有一个边权为正的有向无环图。它具有单个源和一组目标(距离源最远的顶点)。我找到从源到每个目标的最短路径。其中一些路径是重叠的。我想要的是一个最短路径树，它最小化所有边的权重总和。

例如，考虑其中两个目标。假设所有边的权重相等，如果它们在大部分长度内共享一条最短路径，那么这比两条基本上不重叠的最短路径更可取(树中的边越少，总成本就越低)。

另一个例子:两条路径在其长度的一小部分是不重叠的，对于不重叠的路径具有高成本，但对于长共享路径的成本低(低组合成本)。另一方面，两条路径的大部分长度是不重叠的，非重叠路径的成本较低，但较短的共享路径的成本较高(也是低组合成本)。有很多组合。我希望找到总体成本最低的解决方案，给定从源到目标的所有最短路径。

换句话说，我想要最短、最短路径树。

有没有人对此有什么印象？有人能告诉我相关的算法或类似的应用吗？

干杯!

Answer 1

这个问题(Steiner Tree)是NP难的，也是最大SNP完全的，因此除非P=NP，否则既没有多项式时间算法，也没有任意闭合近似( PTAS )。

MST可以给出一个比最优的权重任意差的权重，除非你知道你的图的一些特殊特征(例如，图是平面的，或者至少权重符合三角形不等式)。例如，如果所有边权重均为1且只有一个目标的K_1,000,000,001，则最优解决方案的权重为1，而MST的权重为1,000,000,000。

如果假设目标之间的所有边以及源和每个目标之间的所有边都存在，则仍然可以按任意因子超调。考虑上面的例子，但是将目标和源之间的边权重更改为2,000,000,000,000,000,000 (距离最优仍然相差十亿倍)。

当然，您可以通过遍历图来将图转换为“移除”时间为O(E)或更高的边权重。这加上目标和源集合的MST，得到的近似比为2。

存在更好的近似比。Robins和Zelikovsky有一个多项式时间算法，它永远不会比最优算法差54.94%：http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik & Chlebikova表明，近似小于1.05%是NP-hard：The Steiner tree problem on graphs: Inapproximability results (DOI10.1.1.4.1339)

如果你的图表是平面的，情况会更好。由于Borradaile，Kenyon-Mathieu和Klein (在Erickson，Monma和Veinott基础上构建)，有一个快速算法可以给出任意接近的近似：An O(nlogn) approximation scheme for Steiner tree in planar graphs (DOI10.1.1.133.4154)

Answer 2

如果您只有正成本，并且正在最小化，则只需使用Dijkstra's algorithm即可。