3
$\begingroup$

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:

  1. 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.
  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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 21, 2018 at 18:07
  • $\begingroup$ 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). $\endgroup$
    – Z2VCv
    Jun 22, 2018 at 0:41

1 Answer 1

Reset to default
3
$\begingroup$

  1. Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).

  2. Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$.

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

enter image description here

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

enter image description here

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$
    – Z2VCv
    Jun 22, 2018 at 0:43
  • $\begingroup$ @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. $\endgroup$
    – Clement C.
    Jun 22, 2018 at 0:45
  • $\begingroup$ 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. $\endgroup$
    – Z2VCv
    Jun 22, 2018 at 0:49
  • $\begingroup$ @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. $\endgroup$
    – Clement C.
    Jun 22, 2018 at 0:55
  • $\begingroup$ 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)? $\endgroup$
    – Z2VCv
    Jun 22, 2018 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.