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)