两个指定顶点之间最短两个不相交的路 [英] Shortest two disjoint paths between two specified vertices

问题描述

给出一个加权无向图<强G 和两个顶点的 A，B ，我们要找出两条路径 - > B 和<强> B - >一使得它们不共享任何边缘，并使得边缘的权重的两个路径​​的总和是最小的。最多可以为 1000 顶点，最高的 10,000 的边缘。

Given a weighted undirected graph G and two vertices a, b, we want to find two paths a -> b and b -> a such that they don't share any edge, and such that the sum of weights of edges in both paths is minimum. There can be up to 1,000 vertices, and up to 10,000 edges.

我最初曾试图想出一个动态规划方法，也没有找到这样的。任何意见/建议将是非常美联社preciated。

I had initially tried to come up with a dynamic programming approach, but couldn't find such. Any ideas/suggestions would be extremely appreciated.

推荐答案

这是最小代价流问题 。您可以将流量为每边等于1，然后搜索之间的 和 B 成本最低的流量与流量= 2。

This is Minimum-cost flow problem. You can assign flow capacity for each edge equal to 1, then search for a minimum-cost flow between a and b with flow=2.

有人可能会认为它是可以使用一个简单的算法来找到从最短路径 为 B ，从图中删除其边缘，然后找到另一最短路径

Someone may think that it is possible to use a simple algorithm to find shortest path from a to b, remove its edges from the graph, then find another shortest path.

此方法并不总是最佳的。对于一些图表它提供了一个很好的近似。对于其他人可能会给出一个非常糟糕的解决办法：

This approach is not always optimal. For some graphs it gives a good approximation. For others it may give a very bad solution:

下面取出的第一最短路径（绿色）边后，剩下的唯一路径（红色）是非常沉重的。这个解决方案的成本是1 + 1 + 10 + 1 + 1 + 2 + 90 + 2 = 108。而最佳成本是1 + 15 + 1 + 2 + 1 + 10 + 1 + 2 = 32

Here after removing edges of the first shortest path (green), the only remaining path (red) is very heavy. The cost of this solution is 1+1+10+1+1+2+90+2=108. While optimal cost is 1+15+1+2+1+10+1+2=32.

这篇关于两个指定顶点之间最短两个不相交的路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！