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). —David Eppstein (talk) 19:35, 25 January 2019 (UTC)