Shortest path with even number of edges

Question

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 ?

Answer 1

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|).

Answer 2

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.