Yen's k shortest paths algorithm

Question

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?

Answer 1

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

• Rafi Goldfarb: Mark as answer? :)