我有一个带有正边权的有向无环图 . 它有一个源和一组目标（距离源最远的顶点） . 我找到了从源到每个目标的最短路径 . 其中一些路径重叠 . 我想要的是一个最短路径树，它最小化所有边缘的权重总和 .
例如，考虑两个目标 . 给定所有边缘权重相等，如果它们在其大部分长度上共享单个最短路径，那么这优于两个大多数非重叠的最短路径（树中较少的边缘等于较低的总成本） .
另一个例子：两条路径长度的一小部分不重叠，非重叠路径的成本高，但长共享路径的成本低（组合成本低） . 另一方面，两条路径在其大部分长度上不重叠，非重叠路径的成本低，但短共享路径的成本高（同样，组合成本低） . 有很多种组合 . 考虑到从源到目标的所有最短路径，我想找到总体成本最低的解决方案 .
换句话说，我想要最短，最短的路径树 .
这会和任何人敲响吗？有人能指出我相关的算法或类似的应用程序吗？
干杯!
2 回答
这个问题（Steiner Tree）是NP-hard和max SNP-complete，因此除非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
Chlebik＆Chlebikova表明近似接近1.05％的是NP难：The Steiner tree problem on graphs: Inapproximability results（doi 10.1.1.4.1339）
如果您的图表是平面的，情况会更好 . 由于Borradaile，Kenyon-Mathieu＆Klein（ Build 于Erickson，Monma和Veinott），有一种快速算法可以给出任意近似的近似值：An O(nlogn) approximation scheme for Steiner tree in planar graphs（doi 10.1.1.133.4154）
如果您只有正成本且最小化，请使用Dijkstra's algorithm .