Talk:K shortest path routing

K other paths

In the introduction it reads "The algorithm not only finds the shortest path, but also K other paths in order of increasing cost." Finding "also K other paths" would mean there are K+1 paths in total. The sentense should correctly read "also K-1 other paths" or "not only finds the shortest path, but as many as K paths in order of increasing cost.". 37.120.105.211 (talk) 15:01, 3 June 2014 (UTC)

Complexity of k-shortest path problems

For all variants of k-shortest path problems, a simple mention of complexity is also needed (classification as P, NP complete etc). It is quite helpful but currently missing. — Preceding unsigned comment added by Qx2020 (talk • contribs) 02:43, 28 December 2015 (UTC)

"Eppstein's algorithm provides the best results"

What is the exact meaning of the claim above? The reference that should support this claim is an Eppstein's article from 1998. We are now in 2016 and a proof shall come after reviewing all works on this type of algorithm for the last 18 years.--109.245.77.202 (talk) 13:05, 10 August 2016 (UTC)

• The sentence makes no sense. See, for example, here:
  • Computing the K Shortest paths: a New Algorithm and an Experimental Comparison by Victor M Jimenez and Andres Marzal: "Experimental results show that the algorithm outperforms in practice the algorithm by Eppstein and by Martins and Santos for different kinds of random generated graphs" or
  • Replacement Paths and k Simple Shortest Paths in Unweighted directed Graphs by Liam Roditty and Uri Zwick: "Eppstein [5] gave an O(m+nlogn+k) time algorithm for the directed version of the problem. However the paths returned by Eppstein's algorithm are not necessary simple, i.e. they may visit certain vertices more than once. In the k simple shortest path problem, the paths returned should be all simple. Katoh et all [11] gave an O(k(m+nlogn)) time algorithm for solving the k simple shortest paths problem for undirected graphs" or
  • Finding the k Shortest Simple Paths; A new Algorithm and its Implementation by John Hershberger, Matthew Maxel and Subash Suri in Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments by Richard E. Ladner (ed), SIAM, 2003 p. 26-36: The k shorthest paths problem in which paths are not required to be simple turns out to be significantly easier. An O(m+knlogn) time algorithm has been known since 1975 [3]; a recent improvement by Eppstein essentially achieves the optimal time of O(m+nlogn+k) - the algorithm computes an implicit representation of the paths, from which each path can be output in O(n) additional time [2]--Vujkovica brdo (talk) 06:55, 23 August 2016 (UTC)
  • Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling by Takuya Akiba, Takanori Hayashi, Nozomi Nori, Yoichi Iwata and Yuichi Yoshida, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015
    Eppstein (Eppstein 1998) improved the time complexity to O(n+m+k) and O(n log n+m+k) on unweighted and weighted graphs respectively, but his algorithm remains prohibitively slow.--Vujkovica brdo (talk) 18:29, 13 September 2016 (UTC)

This question and the response seems to be conflating three different considerations. (1) Does the algorithm achieve the best possible and best known theoretical worst-case time complexity? Clearly yes. My interpretation of the sentence is that this is the intended meaning, but if so it should be written less ambiguously. (2) Do implementations of the algorithm achieve better empirical performance than other algorithms? That depends on the implementations, on the test data, and on the number of paths one seeks. It's a question that can only be answered by experiment, not by the theory in the original paper (which did not include any experiments), and experimental results by others have been mixed. So for this intended meaning, the sentence should be rewritten to say what reliable sources (published experiments such as the one by Jimenez and Marzal) say. (3) Is k shortest paths the correct problem to be solving, or do you really want k shortest simple paths? For k shortest simple paths the algorithms are unambiguously slower, but the results probably more useful for most applications. In some cases (when the input is a DAG, as happens for instance in applications in hypothesis generation for natural language processing) the extra complexity of a simple paths algorithm is just wasted effort, because the paths are automatically simple. And in some cases the extra speed of a k shortest paths algorithm may make up for the fact that some of the paths you get as output are non-simple and undesired. I don't know of experiments that look at this issue, and unless we have references to those we should only describe the difference between the two different problems and their runtimes (both theoretical and empirical) without making editorial judgments about which is better. —David Eppstein (talk) 19:17, 23 August 2016 (UTC)

For k shortest simple paths the algorithms are unambiguously slower! Comparing apples to pears. Your algorithm cannot be used for this purpose. Mentioning DAG above -what it has to do with your algorithm? Bottom line: in practice your algorithm is outdated, of insignificant theoretical importance, solves the easier part of the addressed problem.--Vujkovica brdo (talk) 17:44, 26 August 2016 (UTC)

I might be wrong, but...

The initial version of this article is written by Ccalcmen (David Eppstein's alias ?) in December 2012 advertising Eppstein's algoritm at several points in the article.

Eppstein's algorithm is an improvement of well-known B.L. Fox's work from 1975 (K-th shortest paths and applications to probabilistic networks in Operations Research, Vol. 23. B263–B263). The Fox's k-shortest path problem solution (cycles allowed) has O(m + kn logn) asymptotic time complexity. The same algorithm was improved by Eppstein in 1999 (Finding the K Shortest Pathsin SIAM J. Comput. 28, 2 ,Feb. 1999) and his approach maintains an asymptotic complexity of O(m+n logn+k). Eppstein's algorithm computes an implicit representation of the paths, from which each path can be output in O(n) extra time.

In 2007 John Hershberger, Matthew Maxel, and Subhash Suri. (Finding the k shortest simple paths: A new algorithm and its implementation in ACM Transactions on Algorithms (TALG) 3, 4 (2007), 45.) proposed a replacement paths algorithm, an improved implementation of Eppstein’s algorithm with O(n) improvement in time.

In 2015 Takuya Akuba, Takanori Hayashi, Nozomi Nori, Yoichi Iwata and Yuichi Yoshida (Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence) found the Eppstein algorithm prohibitively slow and devised their indexing method, i.e., they first constructed a data structure called an index from a graph and then top-k distances between arbitrary pairs of vertices were rapidly obtained using the index.

The bottom line - the claims "David Eppstein's algorithm achieves the best running time complexity" and "Eppstein's algorithm provides the best results" are baseless.

Further, the table of the "Important works on the k shortest paths problem" is arbitrary written and incomplete. It does not list 21st century works and authors. The same is valid for Eppstein's BibTeX database http://www.ics.uci.edu/~eppstein/bibs/kpath.bib--Dishonesty Test (talk) 19:25, 25 January 2019 (UTC)

My only edits to this article (or anywhere else in Wikipedia) are the ones under my own name. I have this one watchlisted but have mostly stayed away from editing it (except for some reference and external link cleanups) because of the obvious COI. I have no idea of the real-life identity of Calcyman. You need to see WP:AGF (and maybe also WP:OUTING, and maybe consider changing your user name to something that isn't a blatant violation of AGF, assuming per AGF that you aren't just another sock of Vujkovica brdo). As for the database: I haven't updated it since 2001. Instead, I have a much more recent survey paper with updated (but still by now out of date) references: http://bulletin.eatcs.org/index.php/beatcs/article/view/322 Incidentally, if I were promoting my own work here, I would add my 2017 paper with Kurz (too recent for the survey) showing that the k shortest simple paths can be found in log time per path in graphs of bounded treewidth: https://doi.org/10.4230/LIPIcs.IPEC.2017.16 —David Eppstein (talk) 19:35, 25 January 2019 (UTC)

I did not say David Eppstein wrote this article, rather I had and have now reasonable doubts. Ccalcmen wrote the article initial version advertising D. Eppstein's work as the best one - as the solution of the k-shortest path problem (cycles allowed)- and linked the article to D. Eppstein's BibTeX database query and then dissapeared. We all have access to different powerful search engines that can be used to query any scientific database in order to extract relevant scientific information. Earlier and on this page, D. Eppstein defended this advertisement. Further David Eppstein (auto?)biography linked Eppstein's algorithm to this article. The good faith assumption should include B.L. Fox's work which D. Eppstein improved as it was described above, then Hershberger et all further improvement of the D. Eppstein's work and Akuba et all rejection of the D. Eppstein's algorith as prohibitlvely slow in practice and their indexing method and many other names and results related to this problem published before and after 1999.--Dishonesty Test (talk) 09:12, 28 January 2019 (UTC)

This is pretty low-grade trolling. Either make an actionable proposal to improve the article or move on. No one cares about your thoughts on other editors but I will have this removed if you continue with the off-topic crap. Johnuniq (talk) 09:31, 28 January 2019 (UTC)

The comment above is insulting and primitive. My comments are not about other editors and other editor(s) is(are) mentioned in the COI violation sense only. Necessary actions leading to the article content improvement are contained in my comments above:

• remove the table of the "Important works on the k shortest paths problem"
• remove the claims "David Eppstein's algorithm achieves the best running time complexity" and "Eppstein's algorithm provides the best results"
• remove the Eppstein's BibTeX database query (http://www.ics.uci.edu/~eppstein/bibs/kpath.bib)
• add to the First variant: In the first variant, the paths are not required to be loopless (this is the simple one): The first solution of this problem is given by B.L. Fox in 1975. The Fox's k-shortest path problem solution has O(m + kn logn) asymptotic time complexity. The same algorithm was improved by Eppstein in 1999 and his approach maintains an asymptotic complexity of O(m+n logn+k). Eppstein's algorithm computes an implicit representation of the paths, from which each path can be output in O(n) extra time. In 2007 Hershberger et all proposed a replacement paths algorithm, an improved implementation of Eppstein’s algorithm with O(n) improvement in time. In 2015 Akuba et all found the Eppstein algorithm prohibitively slow and devised their indexing method, i.e., they first constructed a data structure called an index from a graph and then top-k distances between arbitrary pairs of vertices were rapidly obtained using the index.
• If I do not see a valid academic objection to my proposal within a week or so, I'll update the article accordingly.

--Dishonesty Test (talk) 12:53, 28 January 2019 (UTC)

It is incorrect to call my algorithm "the same algorithm" as Fox, merely improved. They are quite different algorithms for the same problem. It is also incorrect to say that the first solution was by Fox. See Hoffman and Pavley JACM 1959. My method is more closely related to theirs than to Fox's. —David Eppstein (talk) 16:57, 28 January 2019 (UTC)

References