如何最小化最短路径树的总成本

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

例如，考虑其中两个目标。假设所有边的权重相等，如果它们在大部分长度上共享一条最短路径，那么这比两条几乎不重叠的最短路径要好（树中的边越少，总成本越低）。

另一个例子：两条路径在其长度的一小部分内不重叠，不重叠路径的成本较高，但长共享路径的成本较低（组合成本较低）。另一方面，两条路径在其大部分长度上都是不重叠的，非重叠路径的成本较低，但短共享路径的成本较高（而且组合成本较低）。有很多种组合。考虑到从源到目标的所有最短路径，我希望找到总体成本最低的解决方案。

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

这对任何人来说都敲响了警钟吗？谁能向我指出相关算法或类似应用程序？

Cheers!

这个问题 （斯坦纳树 http://portal.acm.org/citation.cfm?id=1414423) 是 NP 困难且最大 SNP 完全的，因此除非 P = NP，否则既不存在多项式时间算法，也不存在 PTAS（任意接近的近似）。

MST 可以给出比最佳权重任意差的权重，除非您知道图的某些特殊特征（例如图是平面的，或者至少权重服从三角不等式）。例如，如果您有 K_1,000,000,001，所有边权重均为 1，且只有一个目标，则最优解的权重为 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 http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik 和 Chlebikova 表明，接近于 1.05% 是 NP 困难的：图上的斯坦纳树问题：不可近似性结果 http://portal.acm.org/citation.cfm?id=1414423（doi 10.1.1.4.1339）

如果你的图表是平面的，情况会更好。 Borradaile、Kenyon-Mathieu 和 Klein（基于 Erickson、Monma 和 Veinott）提出了一种快速算法，可以给出任意接近的近似值：平面图中 Steiner 树的 O(nlogn) 近似方案 http://portal.acm.org/citation.cfm?doid=1541885.1541892（DOI 10.1.1.133.4154）