Another solution that doesn't require modifying the algorithm (so you can do it with an off-the-shelf implementation):
Have two copies of the graph, one called
even the other called
odd. The idea is that when the total path-length so far is even/odd, you'll be in the
odd graphs respectively. Then you only need to consider the start/end nodes on the
You can do this by removing the odd-length edges from both graphs, and replacing them with equivalent edges that criss-cross graphs. This works because adding an odd number swaps parity, while adding an even number keeps the same parity.