How to find the minimum weighted cycle containing two given nodes in a weighted undirected graph?

3
votes

Given a weighted undirected graph G = (V, E) and a set of nodes P.

Given two nodes, n1 and n2.

I want to find two separate (non-overlapping) paths from n1 to n2, so that the sum of the weights of the two paths is minimum. And I paraphrase the problem to what the title describes, that is the minimum weighted cycle containing n1 and n2.

Obviously it's not correct to find a first minimum weighted path p1 from n1 to n2 and then remove the edges in p1 from the graph and then find a second minimum weighted path p2.

How can I find such a cycle?

1
algorithmgraphcycleshortest-path
What have you got so far? – fuesika
@fuesika no idea yet..:( – Tian Wang
@fuesika It's a typical min cost max flow problem. You can also search for the answer of the problem which describe a same situation as my problem. – Tian Wang

1 Answers

1
votes

The problem can be solved using flow networks. See the Edmonds-Karp algorithm: it involves computing augmenting paths at each step.

Find an augmenting path, like described in the Edmonds-Karp algorithm, using a breadth first search (if your graph is weighted, use Bellman-Ford).

Then, find another augmenting path in the same way. Eliminate the edges that appear in both paths (the flow algorithm will actually take care of this for you), and that will be your cycle. Basically, if you set all your edges to capacity 1, your cycle will consist of the edges you've pushed 1 flow over.

If you don't like the flow-based solution, here's another. It's basically the same thing, just not in terms of flow algorithms.

  1. Find a shortest path n1 -> n2 with any algorithm that can do this (Dijkstra if no negative costs, Bellman-Ford otherwise);

  2. Replace the edges of this shortest path with directed arcs directed from n2 towards n1. For example, if your shortest path is n1 -> x -> y -> z -> n2, replace the edge (n1, x) with the directed arc x -> n1, (x, y) with the directed arc y -> x etc.

    Also negate the costs of these arcs. For example, if (x, y) had cost c, the directed arc y -> x will have cost -c.

  3. Find a shortest path from n1 to n2 in this new graph. You'll have to use an algorithm that works with negative edges now.

  4. Remove the edges that appear in both of the shortest paths. What you're left with is the cycle you're after.