Finding shortest path between nodes with a twist

Question

Note: if you feel that I should include code, please tell me.

I am solving a problem of finding shortest path between nodes. I am given the vertices between nodes, however they are one sided (ie you can go from A to B, but not from B to A). The twist of the challenge, is that the paths (vertices) taken must be even number. I am able to find the path, however I am confused what to do when it is not even number. I assume next I should find some sort of loop to get the desired even amount of vertices covered (as you can go through same node more than once), however I don't know how to do it.

Answer 1

Just transform your graph to something that can be searched easily!

How?

Given a a graph X {A, E} (A being the set of vertices, E being the set of (directed) edges), construct a graph X' {A, E*}, such that an edge is in E* (from point B to point D) iff there is a pair of edges in E such that the first is from B to C, and the second - from C to D.

You may also want to keep a reverse mapping for edges (I.e. how was the edge constructed?)

How difficult is this?
Potentially up to N^3 where N is the number of vertexes, depending on your graph structure. Given that path search algorithms are usually in the order of N^2 to N^3, that should be fine. Also N^3 is the naive way - you may be able to find a better way.

What do I do with it?
Given this new graph - Any even-length path in X is a path in X' if you throw out every odd vertex. Also - any path through X' is an even-length path through X if you fill in the gaps via the reverse mapping from the first section. I.E. You have a surjection from even-length paths in X to paths in X'.

This surjection also preserves path length comparison - a path K' is longer that a path L' in X' iff their corresponding paths in X - K and L - have the same relationship, i.e. K is longer than L.

Eh... OK, so what?
Well all this theory lets you claim one neat thing - the shortest path through X' is going to have a corresponding shortest even-length path through X. This graph is going to have the same number of vertexes, and maybe a larger or smaller number of edges. Hence any of the numerous path-finding algorithms will work - your question implies you can use those already.

Can I do all this without the extra graph?
Why yes! Of course you can! Just use your imagination! As in - don't explicitly construct the extra graph. Just imply it. This will require changes to the actual path searching algorithm - when asked about nodes adjacent to some given node, instead of listing everything connected directly - list everything connected through exactly 2 edges.

Depending on your situation this may or may not be a better solution. The "theoretical" one allows usage of search algorithms out-of-the-box, but suffers from a lot of setup. The second one mitigates setup at the cost of modifying the algorithms (and IMHO has more room for mistakes)

Answer 2

(I assume you mixed up the term "vertices" with "edges", a graph typically consists of vertices = nodes, with edges between them).

I would try something along the lines of the following idea:

• from your initial graph, construct a new one containing the same nodes, but different edges

• you draw an edge in your new graph between two nodes A and B, when there is a two-step path from A to B in your original graph. This should be easy to construct by running a simple depth-first search on each node with a limited depth of 2. If your original graph had weighted edges, assign the new edges the sum of the weights of the two corresponding edges from the original graph

• now you can apply a standard shortest-path algorithm to this new graph

• from the solution found it should be trivial to construct the corresponding path im the original graph

This works because every path with an even number of edges in your original graph can be split up into sub-paths of length 2.