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 even
/odd
graphs respectively. Then you only need to consider the start/end nodes on the even
graph.
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.