Talk:Yen's algorithm
Apologies if I am misunderstanding the algorithm, but as stated, I'm not sure what guarantees that a spur path doesn't circle back and intersect a node that is already on the root path, resulting in a cyclic result? Are these to be removed later in an unstated step? Its hard to imagine this scenario in the illustrated example (a directed graph), but particularly with undirected graphs (edges can be traversed both ways) I think this could happen very readily.
Note the following in the original 1971 paper "Finding the K shortest loopless paths in a network": "(b) Apply a shortest-path algorithm to find the shortest path from (i) to (N), allowing it to pass through those nodes that are not yet included in the path" — Preceding unsigned comment added by 184.69.64.162 (talk) 01:26, 5 April 2014 (UTC)
Answer: nodes in the root path are removed from the graph before computing the spur path. — Preceding unsigned comment added by 193.136.33.222 (talk) 18:15, 7 August 2014 (UTC)
A problem with Qk and Qkk
What is the difference between Qk and Qkk? They seem to be the same.
Bug in stop early
The article said we can stop the algorithm if the path number in container B exceed or equal to the amount of paths still need to be found. If the remaining number is K - k, we can just put top K - k paths in B to A and the algorithm is finished. But here is an example.
Nodes: S, Z, T, X1, X2, X3, X4, X5, Y1, Y2, Y3
Edges: S - Z - T, S - X1 - X2 - X3 - X4 - X5 - T, S - Z - Y1 - T, S - Z - Y2 - T, S - Z - Y3 - T
Suppose edge weight all equals 1. Now let's find top 3 path from S to T in this graph.
Of course at first, we get S - Z - T as the shortest path.
Then we add Path: (S - X1 - X2 - X3 - X4 - X5 - T), and Path: (S - Z - Y1 - T) to container B.
Here we notice stop early condition is satisfied. So we stop the algorithm and put paths of container B to container A.
But it is obvious that Path: (S - Z - Y2 - T) is shorter than Path: (S - X1 - X2 - X3 - X4 - X5 - T).
So I suppose it is a bug and we cannot stop early on such condition. Correct me if I misunderstand the algorithm, thanks.