CODEWITHSUNDEEP
algorithmgraph
Felipe
Felipe

Reputation: 697

Shortest path with even number of edges

Given a weighted undirected graph G and two nodes U,V to get the shortest path. How can i get the shortest path from U to V that uses a even number of edges (if possible to get it) ?

I've found some articles on the web speaking that a modification on the original graph is necessary. But i can't understand how to do it.

There is some good material to study on this problem ?

Upvotes: 7

Views: 7968

Answers (3)

Untitled
Untitled

Reputation: 790

  1. Make a copy of your graph with the same weights and call it G'.
  2. Connect every vertex of G to the corresponding vertex in G' and set the weight of the new edges to zero.
  3. Delete copy of u from G' and delete v from G.
  4. Now, the set of edges you added between G and G' constitute a matching M. Take that matching and find a minimum augmenting path for that matching.

Such a path must have u as one of its end points and copy of v as the other endpoint, because they are the only uncovered vertices. If you merge back the copies and get rid of the added edges, the path you found corresponds to an even path, because it starts at one copy and ends at another. Also, every even path corresponds to an augmenting path (by same argument), therefore the minimum of one is also the minimum of the other. This is explained in here.

Upvotes: 3

Vincent van der Weele
Vincent van der Weele

Reputation: 13187

You'll need to build an intermediate graph and run Dijkstra's on that graph.

Given a graph G = (V, E), create a new graph G' = (V', E'), with V' a new set of vertices v_even and v_odd for every vertex v in V and E' the set of vertices as follows: If (u, v) is an edge in G, then (u_odd, v_even) and (u_even, v_odd) are edges in G', with the same weight.

Obviously, the new graph has twice as many edges and vertices as the original graph.

Now, if you wanted to find the shortest path between s and t in G, simply run Dijkstra's on G' to find the shortest path between s_even and t_even.

The running time is still O(|V| log |E|).

Upvotes: 3

Luka Rahne
Luka Rahne

Reputation: 10467

What about running Dijkstra where each node has two values. One is odd (coming from even value) and other is even value.

Upvotes: 0

Related Questions