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)

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 - has to to with your algorithm? Bottom line: in practice your algorithm is outdated, of negligible theoretical importance, solves the easier part of the addressed problem.--Vujkovica brdo (talk) 17:44, 26 August 2016 (UTC)