2

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?

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.