Search code examples
pythonalgorithmgraph-theorydijkstrapath-finding

algorithm - Path finding through a specific vertex

I am looking for a way to find a loopless path (preferably shortest path, but not necessarily though) from a source vertex (S) to a destination vertex (D) that passes through another specific vertex (X) somewhere in the graph.

Now, before you point me to Finding shortest path between pass through a specific vertex I want to say that this solution ignores the case when the shortest path from S to X already includes D, which is a possible scenario in where I am applying this algorithm. How would you solve this problem in that case?

What I tried was a naive attempt to look for such paths in the results of Yen's K shortest paths algorithm. But I am hoping there is a more efficient and certain way to do that.

Again, just to point it out, I am not necessarily looking for the shortest path from S to D through X, but just any loopless path, although shortest path would do better.

Solution

  • The basic concept is quite simple; then you get to adapt for cases that loop into and out of X on their shortest remaining paths.

    • Remove D from the graph.
    • Find P1, the shortest path from S to X.
    • Restore D to the graph.
    • Remove all nodes in P1.
    • Find P2, the shortest path from X to D.
    • return P1 + P2.

    That's the gist of the solution.

    NOTE: you may find that removing P1 yields a sub-graph with no remaining path to D. In this case, you will want a dynamic programming solution that searches through the idea above, but with backtracking and another method to search for P1 candidates.

    When you first find P1, check that the node you're about to use will not isolate X from D on the second leg of the trip. This will give you a much faster search algorithm.

    Is that enough of a start?

    The need to adapt comes from a case such as this -- consider the graph

    src  dst
 S    1, 2
 1    X, D
 2    D
 X    1

    Your partial paths are

    S -> 1 -> X
S -> 2 -> 3 -> X
X -> 1 -> D
and, incidentally,
S -> 1 -> D

    When you run your shortest-path searches, you get the path S 1 X 1 D, rejected because of the loop. When you implement my first modification -- remove node 1 when trying to find a path X to D, there is no remaining path.

    The algorithm needs the ability to back up, rejecting the path X 1 D to find X 2 3 D. That's the coding that isn't immediately obvious from the description.

    Here's a mental exercise for you: is it possible to construct a graph in which each shortest path (S to X and X to D) isolates the other terminal node from X? In my example above, you can simply switch the process: when the S to X path isolates D, then start over: first find X to D, remove node 1, and then find S to X in the remaining graph. Can you find a graph where this switch doesn't work, either?

    If not, you have an immediate solution. If so, you have a more complex case to handle.