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:
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?