Direct
I answered this here:
https://stackoverflow.com/questions/11900830/using-floyd-warshall-algorithm-to-determine-an-odd-matrix/11902296#11902296
Basically:
- 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
- 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:
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)
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.