<ol>
<li><p><a href="https://pubsonline.informs.org/doi/abs/10.1287/mnsc.17.11.712" rel="nofollow noreferrer">Yen's original paper</a> <a href="https://i.sstatic.net/lepmO.png" rel="nofollow noreferrer">1</a>, from <em>1971</em>, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).</p></li>
<li><p><a href="https://pubsonline.informs.org/doi/abs/10.1287/mnsc.18.7.401" rel="nofollow noreferrer">Lawler's original paper</a> <a href="https://i.sstatic.net/yGtah.png" rel="nofollow noreferrer">2</a>, from <em>1972</em>, improves the time complexity upper bound to $O(Kn^3)$.</p></li>
<li><p><a href="https://en.wikipedia.org/wiki/Yen%27s_algorithm#Time_complexity" rel="nofollow noreferrer">Wikipedia's analysis</a> 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 <em>1984</em>. [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 <strong>Wikipedia is not considering the same problem.</strong></p></li>
</ol>

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

<p>See for instance this quote from Yen's paper (Section 5):</p>

<p><a href="https://i.sstatic.net/yGtah.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/yGtah.png" alt="enter image description here"></a></p>

<p>and this one for Lawler's paper (Section 5):</p>

<p><a href="https://i.sstatic.net/lepmO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lepmO.png" alt="enter image description here"></a></p>

<hr>

<p><a href="https://i.sstatic.net/lepmO.png" rel="nofollow noreferrer">1</a> <em>Finding the K Shortest Loopless Paths in a Network,</em> Jin Y. Yen (1971).
Management Science 197117:11 , 712-716 </p>

<p><a href="https://i.sstatic.net/yGtah.png" rel="nofollow noreferrer">2</a> <em>A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem</em>, 
Eugene L. Lawler (1972). Management Science 197218:7 , 401-405 </p>

<p>[3]  <em>Fibonacci heaps and their uses in improved network optimization algorithms</em>. 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.</p>

CC BY-SA 4.0
2018-06-22T00:43:38.620Z
Ah, I see, I was missing that Fibonacci heaps were non-existent at the time of the algorithms publishing. I'm not sure, but can you still elaborate on point 3 from my question? I don't understand how/why that would affect time complexity for yen's algorithm using fib heaps(I can't find this online either).
Z2VCv
CC BY-SA 4.0
2018-06-22T00:45:34.507Z
@Z2VCv read my answer again. The main point is not the Fibonacci heap. The point is that the problem for which Lawler's paper gives an improvement is the general weight case, while Wikipedia only talks about the non-negative-weight case.
Clement C.
CC BY-SA 4.0
2018-06-22T00:49:12.277Z
Indeed, I understand that. So do you mean to say that in case edge weights are positive (and dijkstra is used with/without fib heaps), the time complexity is unaffected?

I'm still not very clear why it would affect it in case edges can be negative weighted(since as in normal bellman-ford, you must relax edges the same way), but perhaps I will think about it after I assert the case of positive weight edges.
Z2VCv
CC BY-SA 4.0
2018-06-22T00:55:51.030Z
@Z2VCv I mention the Fibonacci heap part to hint that Wikipedia does a poor job at retracing the history and put things in context (and in particular... why do they even mention Lawler's improvement in a page where they only care about positive edges, when the Yen's algorithm is as good?). Now, in the worst case (dense graphs) $m=\Theta(n^2)$ and Dijkstra is still $n^2$. The crucial point is that Dijkstra (non-negative edges) leads to an extra $O(n^2)$; Bellman-Ford and others (arbitrary edges) lead to an extra $O(nm)=O(n^3)$. So Yen's algorithm is $O(Kn^4)$-time for the general case.
Clement C.
CC BY-SA 4.0
2018-06-22T00:59:04.597Z
Yes, as I said I understand that. I just need someone to confirm my assertion that "Lawler's modification have no benefits in case edge weights are positive, regardless of how we implement dijkstra(using or not using fib heaps)", and then my logical next question is how Lawler's modification can do any benefit in case of negative weighted edges? Do we smartly skip/modify the inner bellman ford function call? If so, how? And why is the same method not applicable to dijkstra function call(in case of only positive weight edges)?
Z2VCv
CC BY-SA 4.0
2018-06-22T01:01:08.600Z
My apologies if I'm not being very clear, feel free to ask for any clarification, english is not my native language :)
Z2VCv
CC BY-SA 4.0
2018-06-22T01:13:28.103Z
@Z2VCv I would suggest you read Lawler's paper; it is quite short. As far as I can tell by skimming it quickly: while Yen's algorithm uses Dijkstra (or Bellman-Ford) as a blackbox and calls it $O(Kn)$ times (which would not be improvable), Lawler's idea is to use something like Floyd-Warshall for a different (but related) problem, and call it only $K$ times.
Clement C.
CC BY-SA 4.0
2018-06-21T18:45:06.550Z
2018-06-21T20:40:36.227Z
2018-06-21T20:40:36.227Z
Clement C.
<p>I recently read about <a href="https://en.wikipedia.org/wiki/Yen%27s_algorithm#Pseudocode" rel="nofollow noreferrer">Yen's algorithm</a>, I understand the algorithm and it seems correct, however <a href="https://en.wikipedia.org/wiki/Yen%27s_algorithm#Lawler&#39;s_modification" rel="nofollow noreferrer">Wikipedia mentions</a> 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:</p>

<ol>
<li>According to <a href="https://pubsonline.informs.org/doi/abs/10.1287/mnsc.18.7.401" rel="nofollow noreferrer">the original research paper</a>, 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.</li>
<li>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?</li>
<li>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.</li>
<li>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).</li>
</ol>

<p>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.</p>

CC BY-SA 4.0
2018-06-21T18:07:26.760Z
Wikipedia is not a primary source.  If there seems to be some discrepancy, I'd suggest starting by reading the original papers.  This question seems very focused on Wikipedia; what happens if you forget about Wikipedia, assume Wikipedia is fallible, and read Yen's and Lawler's original papers and try to understand the situation on your own?  Requests for code are off-topic here.
D.W.
CC BY-SA 4.0
2018-06-22T00:41:29.977Z
Hi @D.W. I see why you think request for code is off-topic, so I think I should note that I'm more looking forward to pseudocode/some other resource which just explains the modification better. Thank you for the idea to ignore Wikipedia completely, I'll try to understand the papers that way(but I just find it too hard and confusing generally).
Z2VCv
<graph-theory><graph-algorithms><shortest-path>
What exactly is Lawler's modification to Yen's algorithm and how does it work?
Z2VCv
# What exactly is Lawler's modification to Yen's algorithm and how does it work?

(Asked by: username_0 on 2018-06-21)

I recently read about [Yen's algorithm](https://en.wikipedia.org/wiki/Yen%27s_algorithm#Pseudocode), I understand the algorithm and it seems correct, however [Wikipedia mentions](https://en.wikipedia.org/wiki/Yen%27s_algorithm#Lawler's_modification) 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:

1. According to [the original research paper](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.18.7.401), 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.
2. 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?
3. 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.
4. 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.

**Tags:** graph-theory, graph-algorithms, shortest-path

> **Comments:**
> **username_1**: Wikipedia is not a primary source.  If there seems to be some discrepancy, I'd suggest starting by reading the original papers.  This question seems very focused on Wikipedia; what happens if you forget about Wikipedia, assume Wikipedia is fallible, and read Yen's and Lawler's original papers and try to understand the situation on your own?  Requests for code are off-topic here.  
> **username_0**: Hi @username_1 I see why you think request for code is off-topic, so I think I should note that I'm more looking forward to pseudocode/some other resource which just explains the modification better. Thank you for the idea to ignore Wikipedia completely, I'll try to understand the papers that way(but I just find it too hard and confusing generally).  

---

## 1 answers

### Answer by username_2 on 2018-06-21. Score: 3 | Accepted answer

1. [Yen's original paper](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.17.11.712) [1](https://i.sstatic.net/lepmO.png), from *1971*, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).
2. [Lawler's original paper](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.18.7.401) [2](https://i.sstatic.net/yGtah.png), from *1972*, improves the time complexity upper bound to $O(Kn^3)$.
3. [Wikipedia's analysis](https://en.wikipedia.org/wiki/Yen%27s_algorithm#Time_complexity) 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):

[![enter image description here](https://i.sstatic.net/yGtah.png)](https://i.sstatic.net/yGtah.png)

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

[![enter image description here](https://i.sstatic.net/lepmO.png)](https://i.sstatic.net/lepmO.png)

---

[1](https://i.sstatic.net/lepmO.png) *Finding the K Shortest Loopless Paths in a Network,* Jin Y. Yen (1971).
Management Science 197117:11 , 712-716

[2](https://i.sstatic.net/yGtah.png) *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.

> **Comments:**
> **username_0**: Ah, I see, I was missing that Fibonacci heaps were non-existent at the time of the algorithms publishing. I'm not sure, but can you still elaborate on point 3 from my question? I don't understand how/why that would affect time complexity for yen's algorithm using fib heaps(I can't find this online either).  
> **username_2**: @username_0 read my answer again. The main point is not the Fibonacci heap. The point is that the problem for which Lawler's paper gives an improvement is the general weight case, while Wikipedia only talks about the non-negative-weight case.  
> **username_0**: Indeed, I understand that. So do you mean to say that in case edge weights are positive (and dijkstra is used with/without fib heaps), the time complexity is unaffected?  I'm still not very clear why it would affect it in case edges can be negative weighted(since as in normal bellman-ford, you must relax edges the same way), but perhaps I will think about it after I assert the case of positive weight edges.  
> **username_2**: @username_0 I mention the Fibonacci heap part to hint that Wikipedia does a poor job at retracing the history and put things in context (and in particular... why do they even mention Lawler's improvement in a page where they only care about positive edges, when the Yen's algorithm is as good?). Now, in the worst case (dense graphs) $m=\Theta(n^2)$ and Dijkstra is still $n^2$. The crucial point is that Dijkstra (non-negative edges) leads to an extra $O(n^2)$; Bellman-Ford and others (arbitrary edges) lead to an extra $O(nm)=O(n^3)$. So Yen's algorithm is $O(Kn^4)$-time for the general case.  
> **username_0**: Yes, as I said I understand that. I just need someone to confirm my assertion that "Lawler's modification have no benefits in case edge weights are positive, regardless of how we implement dijkstra(using or not using fib heaps)", and then my logical next question is how Lawler's modification can do any benefit in case of negative weighted edges? Do we smartly skip/modify the inner bellman ford function call? If so, how? And why is the same method not applicable to dijkstra function call(in case of only positive weight edges)?  
> **username_0**: My apologies if I'm not being very clear, feel free to ask for any clarification, english is not my native language :)  
> **username_2**: @username_0 I would suggest you read Lawler's paper; it is quite short. As far as I can tell by skimming it quickly: while Yen's algorithm uses Dijkstra (or Bellman-Ford) as a blackbox and calls it $O(Kn)$ times (which would not be improvable), Lawler's idea is to use something like Floyd-Warshall for a different (but related) problem, and call it only $K$ times.  

---

