Yen’s K Shortest Paths Algorithm – Overview and Implementation

algorithmsgraphpath finding

I'm currently trying to understand Yen's k shortest paths algorithm. I based myself on the original paper as well as on the Wikipedia article, but still cannot see why it is correct if k > 2. In fact, I don't even see why it works on the following example:

example graph

For instance, let's consider the 3 shortest paths from A to D. Those are A -> B -> C -> D (length 3), A -> B -> F -> D (length 4) and A -> B -> C -> E -> D (length 5). From what I have understood of the algorithm, the 2 shortest paths are computed properly. However, the 3rd shortest path is a deviation from the 2nd shortest path at vertex B and the path A -> B is shared between the 2 shortest path; consequently, if I have understood the algorithm properly, you won't be able to go through B -> C which is the only way you can get a third shortest path. From my understanding, the algorithm will choose instead A -> B -> D (which is the fourth shortest path).

What did I miss?

Best Answer

I think that what is confusing you is the thought that B is emptied at the end of an iteration, where by B I mean the path vector from the wikipedia pseudocode.

After the first iteration B has the below potential paths

B_vec == [A->B->F->D (length 4), A->B->C->E->D (length 5)]

When choosing the 2nd shortest path, the path is popped, but B_vec is not emptied so before the 2nd iteration we have

B_vec == [A->B->C->E->D (length 5)]

After the second iteration we have

B_vec == [A->B->C->E->D (length 5), A->B->D (length 6)]

And A->B->C->E->D is selected

Related Solutions

Randomly generate directed graph on a grid

it's ice, you will move unless you hit a rock.
the only way to change direction is to hit a rock.
if you hit a rock you have to change directions.
cycles are good, for obvious reasons.
there can be multiple starts, and multiple ends.

more advanced properties:

the cells without adjacent rocks are not reachable (some can be traversed)
walls are rocks too, if you remove them, you can decide to wrap around.
you can use sub-grids as patterns ("tiling" 3x3, 3x4, 5x5, ...etc)
you can overlay a puzzle MxN tile on top of non-traversable MxN area and add a rock to redirect in/out of it.
rotation or symmetry of a tile can be interesting
you can expand a tile by inserting icy rows / columns

example:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

example of combining tiles:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

you might like the game Tsuro, it uses tiles to generate a random board.

Am I right about the differences between Floyd-Warshall, Dijkstra’s and Bellman-Ford algorithms

If I understand you correctly, your understanding is correct.

Djikstra's finds the smallest cost path from a source node to every other node in the graph, except if there is a negative weight edge. (Dijkstra's can be transformed easily into the A* algorithm by just changing it to stop once its found the target node and adding heuristics.)
Bellman-Ford does the same as Dijkstra's, but is slower. But it can handle negative weight edges.
Floyd-Warshall finds the cost of the smallest cost path from each node to every other node. (It returns a numeric matrix.) It is far slower than either Djikstra's or Bellman-Ford. Unlike what you wrote, it does not fail when a negative cycle occurs, it just reports a meaningless negative number for the cost of some node to itself.

Best Answer

Related Solutions

Randomly generate directed graph on a grid

Am I right about the differences between Floyd-Warshall, Dijkstra’s and Bellman-Ford algorithms

Related Topic