The shortest path with an even number of edges

Question

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

I found several articles on the Internet saying that modification on the original chart is needed. But I can’t figure out how to do this.

Is there any good material to study this problem?

Answer 1

You will need to build an intermediate chart and run Dijkstra on this chart.

For the graph G = (V, E) create a new graph G' = (V', E') , with V' new set of vertices v_even and v_odd for each vertex v in v and E' 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 want to find the shortest path between s and t in G , just run Dijkstra on G' to find the shortest path between s_even and t_even .

Runtime is still O(|V| log |E|) .

Answer 2

• Make a copy of your graph with the same weights and name it G.
• Connect each vertex G to the corresponding vertex in G 'and set the weight of the new edges to zero.
• Delete a copy of u from G 'and remove v from G.
• Now the set of edges added between G and G is a match M. Take this match and find the minimum path for this match.

Such a path must have u as one of its endpoints and a copy of v as the other endpoint, because they are the only uncovered vertices. If you combine the copies and get rid of the added edges, the path you found matches the even path, because it starts with one copy and ends with another. In addition, each even path corresponds to an increase path (by the same argument), so at least one is also the minimum of the other. This is explained in here .

Answer 3

How about starting Dijkstra, where each node has two meanings. One of them is odd (based on an even value), and the other is even a value.