What exactly is Lawler's modification to Yen's algorithm and how does it work? I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as basically caching all previous Dijkstra calls for the similar spur graphs. I have some questions about it:


According to the original research paper, the algorithm speeds up Yen's algorithm to $O(k \cdot n^3)$, but the Yen's algorithm described by Wikipedia is already of that complexity.
The original research paper actually seemingly contains 5 modifications to the original algorithm, although Wikipedia only describes one of them, what is going on here?
How does the mentioned modification in Wikipedia modify the runtime of the algorithm, according to me, the worst case time complexity is the same, or at most improved by constant time.
The last line of the Wikipedia description states "To perform this operation for $A^k$, a record is needed to identify the node where $A^{k-1}$ branched from $A^{k-2}$ ", but why? Can't we use the cached Dijkstra call from $A^{k-2}$ as well? Why is that bad? Since $B$(from pseudocode) is sorted and length of spur path + root path is increasing, it should never cause a problem? Maybe we are somehow missing testing out a root path + spur path, but it's un-intuitive to me how/why only the modification causes that(and why that wouldn't affect the original algorithm as well).


It would also be nice to get a commented and well tested implementation of the algorithm with the modification for reference, maybe that would make the modification clearer.
Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).
Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$.
Wikipedia's analysis of Yen's algorithm, leading to the $O(Kn(m+n\log n))=O(Kn^3)$ upper bound, is based on the Fibonacci heap implementation of Dijkstra's algorithm, from 1984. [3] But even the $O(n^2)$ upper bound for Dijkstra's algorithm would be fine; the issue, as far as I can tell, is that Wikipedia is not considering the same problem.


Namely, Yen's paper, as well as Lawler's, consider graphs where negative weights are allowed. The Wikipedia seems to restrict itself to non-negative weights, so... one can use Dijkstra there.

See for instance this quote from Yen's paper (Section 5):



and this one for Lawler's paper (Section 5):





1 Finding the K Shortest Loopless Paths in a Network, Jin Y. Yen (1971).
Management Science 197117:11 , 712-716 

2 A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem, 
Eugene L. Lawler (1972). Management Science 197218:7 , 401-405 

[3]  Fibonacci heaps and their uses in improved network optimization algorithms. Fredman, Michael Lawrence; Tarjan, Robert E. (1984). 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934.