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

我有一个具有正边权重的有向无环图。它有一个单一来源和一组目标（离源头最远的顶点）。我发现从源到每个目标的最短路径。其中一些路径重叠。我想要的是使所有边上的权重总和最小的最短路径树。如何最小化最短路径树的总成本

例如，考虑两个目标。如果所有边权重相等，如果他们在大多数长度上共享单一最短路径，那么优于两个大多不重叠的最短路径（树中较少的边等于较低的总成本）。

又如：两条路径是不重叠的对它们的长度的一小部分，与用于非重叠的路径成本高，但成本低的长共享路径（低结合成本）。另一方面，两条路径的大部分长度都不重叠，非重叠路径的成本较低，但短共享路径的成本较高（组合成本较低）。有很多组合。我希望找到具有最低总体成本的解决方案，给出从源到目标的所有最短路径。

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

这是否与任何人响铃？任何人都可以指向相关算法或类似的应用程序吗？

干杯！

来源

2010-05-08 Michael

嗯......尝试分区我不知道。成为与其他人没有任何共同之处的路径。也许反向每一个边缘，并解决补充问题... – 2010-05-08 04:44:50

只需删除那些不在从源到目标的任何路径上的那些节点和边，并计算生成的DAG的最小权重生成树。似乎它会起作用。其中一个答案也提到了它。 – 2010-05-17 18:33:43

似乎这是NP-Complete，MST只是一个红鲱鱼。我发布了一个答案。 – 2010-05-18 03:40:31

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

来源

2010-05-17 18:08:38 Kru

如何使用它并不明显。请详细说明。 -1到那时。另外，为了澄清问题是关于_total_权重（重复计算一次），所以只使用所有最短路径可能无效。 – 2010-05-17 18:37:30

对不起，我误解了这个问题。您可以使用此算法的唯一方法是使用权重来查找近似值，例如新权重是初始值除以可达池的数量。 – Kru 2010-05-18 10:41:31

这个问题（Steiner Tree）是NP-hard和最大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.

存在更好的近似比。罗宾斯& 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（建立在埃里克森，蒙马，& Veinott）：An O(nlogn) approximation scheme for Steiner tree in planar graphs （doi 10.1.1.133。4154）

来源

2010-05-18 14:51:16 Charles

好吧，我没有说在所有情况下（我只是说维基）。无论如何，我删除了这部分。谢谢。无论如何+1为所有参考。我建议你首先添加一个链接，说明它是什么问题。 – 2010-05-18 17:58:53

我已编辑帖子以添加相关链接。 – 2010-05-18 18:18:57

编辑删除对您的陈述的引用。我没有被指责，只是想为读者说清楚。感谢您的链接。 – Charles 2010-05-21 03:15:08

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

回答

相关问题