[Solved]: Shortest path with odd weight

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.