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)

I don't have access to the original paper so I can't verify the pseudocode. What I don't understand is how for statement (`for i from 1 to 2`) works. If it includes the upper limit, or not. Because if it does, the second for `for i from 0 to size(A[k − 1]) − 1:` is not in accord with the comment that says it does not try the last node as a spur node. I now see, that the first for should run only K-1 times, because A[0] already exists. But it is quite confusing, if you see a for having its lower bound `1`, you expect the upper bound be inclusive. TLDR; It might be a good idea to specify the for loops are not upper-bound-inclusive, as there is a for loop beginning with `1`. — Preceding unsigned comment added by 89.177.115.144 (talk) 21:55, 29 August 2017 (UTC)

A problem with Q_k and Q_k^k

What is the difference between Q_k and Q_k^k? 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. — Preceding unsigned comment added by P1erce.dong (talk • contribs) 07:52, 21 January 2017 (UTC)

Pseudo code wrong, non-optimal, and hard to follow.

I recently implemented Yen's algorithm using the pseudo code in the current article. This we unnecessarily arduous because the pseudo code is wrong, non-optimal, and hard to follow.

1. This is wrong

if (totalPath not in B): B.append(totalPath);

it should be

if (totalPath not in A): B.append(totalPath);

2. The potential paths ( B ) need not be sorted. All that is needed is to select the shortest.

3. The use of single character meaningless variable names is extremely confusing.

4. The pseudo code is unnecessarily low level. I suspect it was written with a particuar coding language in mind.

I suggest it should all be replaced by something much easier to follow ( and bug free! )

 IMPORT graph, source and sink
 CLEAR vShortestPaths
 calculate shortest path from source to sink, add to 
 vShortestPaths
 WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE

If anyone is interested here is my C++ implementation https://github.com/JamesBremner/PathFinder/blob/d5a4f94bbd950cf1200b833156db7a78883af539/src/GraphTheory.cpp#L127-L220

 — Preceding unsigned comment added by Ravenspoint (talk • contribs) 17:40, 4 October 2023 (UTC)