我有一个具有正边权重的有向无环图。它有一个源和一组目标（离源最远的顶点）。我找到从源到每个目标的最短路径。其中一些路径重叠。我想要的是一个最短路径树，它可以最小化所有边的权重总和。
例如，考虑两个目标。假设所有边权重相等，如果它们在大部分长度上共享一条最短路径，那么这比两条大多不重叠的最短路径更可取（树中的边越少，总成本越低）。
另一个例子：两条路径在它们的一小部分长度上不重叠，非重叠路径的成本高，但长共享路径的成本低（组合成本低）。另一方面，两条路径的大部分长度不重叠，非重叠路径的成本低，但短共享路径的成本高（同时，组合成本低）。有很多组合。考虑到从源到目标的所有最短路径，我想找到总成本最低的解决方案。
换句话说，我想要最短、最短的路径树。
这是否与任何人敲响了警钟？谁能指出我相关的算法或类似的应用程序？
干杯!
这个问题（Steiner Tree）是 NP-hard 和 max SNP-complete，所以既没有多项式时间算法也没有 PTAS（任意接近的近似值），除非 P = NP。
除非您知道图形的某些特殊功能（例如图形是平面的，或者至少权重服从三角形不等式），否则 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 难的：图上的施泰纳树问题：不可近似性结果 (doi 10.1.1.4.1339)
如果您的图表是平面的，则情况会更好。由于 Borradaile、Kenyon-Mathieu 和 Klein（建立在 Erickson、Monma 和 Veinott 的基础上），有一种快速算法可以给出任意接近的近似值：平面图中 Steiner 树的 O(nlogn) 近似方案 （doi 10.1.1.133.第4154章
如果您只有正成本并且正在最小化，只需使用Dijkstra 算法。