Shortest path with odd weight

Question

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.

We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph.

If possible, describe one algorithm that is reduction-based (that is, make some modification to the graph so that application of Floyd-Warshall, or any other "known" algorithm, and then deciphering the answer will give the result, see http://en.wikipedia.org/wiki/Reduction_(complexity)) and one that is "direct" (that is, make some modification to Floyd-Warshall in order for it to solve this problem).

Answer 1

Direct

I answered this here:

https://stackoverflow.com/questions/11900830/using-floyd-warshall-algorithm-to-determine-an-odd-matrix/11902296#11902296

Basically:

1. Run the algorithm twice (literally a for loop that runs 2 times around the F-W loops) because the path may be longer than the number of vertices
2. Save both the best odd and best even path costs for each pair of vertices - instead of cost[v1][v2] I use cost[v1][v2][evenness].

Proof that running the algorithm twice is sufficient: let's assume a path in the graph has more than 2V vertices -> at least one vertex C must appear 3 times -> it must appear at least twice with the same evenness-of-path-up-to-this-point E. So the path is of the form (with C(E) meaning "vertex C appearing with evenness E"):

P0 - C(E) - P1 - C(E) - P2

where P0, P1 and P2 are segments of the path (perhaps empty). But this path has the same evenness, initial and final state as:

P0 - C(E) - P2

And due to non-negative weights, the former path can't be shorter. So running the algorithm twice is sufficient.

Reduction

From G, create G' in the following way:

1. For each vertex Vi in G, add Vi_odd and Vi_even to G' (a simple implementation is: i_even := 2*i, i_odd := 2*i+1, and the inverse, i = i_either/2)

2. For each edge in G, let Vi be the source vertex, Vj the target vertex, W the weight. If W is odd, add edges (Vi_odd, Vj_even) and (Vi_even, Vj_odd) with weight W. If W is even, add edges (Vi_even, Vj_even) and (Vi_odd, Vj_odd) with weight W.

Run F-W on G'. The weight of the path from Vi_even (initial path weight is 0 = even) to Vj_odd in G' is the weight of the shortest odd path from Vi to Vj in G. The weight of the path from Vi_even to Vj_even is the shortest even path.

Answer 2

Homework? I start with hints. Integer values assumed.

Reduction. Make two copies of the vertices in the graph (odd and even) and rewire the graph such that each odd length edge of the graph is between the even and odd copies.

Direct. The algorithm keeps two values (for each pair of vertices): the length of the even length and odd length shortest paths. You can adapt Floyd if you realize that odd+odd = even (etc).