# Shortest path with odd weight

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

• ATTENTION: The top answers to this post are technically wrong as they find a minimal walk (which may repeat vertices) rather than a minimal path. Finding a minimal path is NP-hard; see J. Abrams' answer. Dec 13, 2021 at 20:33

Direct

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.

• I think you mean to say "weight" when you say "length" throughout, thanks though! May 21, 2013 at 18:12
• Yeah, length, distance, it is all actually supposed to be "weight". I fixed it. May 22, 2013 at 7:58

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

Sorry for digging up this old topic, but all proposed algorithms on this thread are wrong!

This problem is, in fact, NP-hard (and even NP-complete): The paper "Even Cycles in Directed Graphs" by Carsten Thomassen proves in Proposition 2.1 that the problem of finding an odd / even length directed cycle in a digraph through a given edge (!) is NP-complete. Now, we can in fact solve this problem using the algorithm described in this thread: Choose weight = 1 for every edge. Let e be the selected edge that an even cycle should pass through, say e = (v,w). Now, find an odd path from w to v. This path exists if and only if there exists an even cycle through e. This shows that this algorithm must be wrong.

I believe that the suggested algorithm does return an odd-length WALK though, but not a path (vertices may be repeated).