I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of it. And did read about other implementations with the help of http://liinwww.ira.uka.de/bibliography/Theory/k-path.html

But in every paper there is a reference to multiple others citing improved performance in a different scenario. Ultimately too many options and tough to choose one. Hence can some one please provide the reference to most optimized sequential version of finding k-shortest path.


EDIT: Another problem with improved implementation of yen's algorithm is that one cant work with it in parallel. i.e. if I am finding kth shortest path from node 1 to node 100, then in mean time I cannot use it to find from a node to some other node. This is because it removes some nodes and arcs from graph in midst of computation.

The problem with eppstein again is that it uses its own data structure. There are many issues with it. Firstly I will have to construct it to use and the graph in my case is a large graph. The data structure is different for the start and terminal nodes respectively and same data structure cannot be used for other pair. Ultimately resulting in high memory utilization when using multiple instances of the algorithm.

EDIT2: Sorry, this is my fault for lack of clarity, What I basically meant was that One should be able to run multiple instances of the algorithm in parallel. With improvised version of Yen algorithm one cannot do that. Basically a sequential algorithm that can have multiple instances (instances and not parallelism in the algorithm) of it running in parallel.

Secondly, in EDIT1, both of the comments are not a comparison but rather a small discussion. Due to inability to find satisfactory loopless shortest paths, I came across Prof.Eppstein paper compromising on loops for performance. What I am basically looking for is a loopless k-shortest path sequential algorithm with less memory utilization (in my case I am dealing with large road networks) which can scale for very large graphs (over 50k nodes).

Thanks a lot.

  • $\begingroup$ a interesting case study in this area is the netflix contest where $1M was paid for a 10% improvement. it was found after several years of intense work but involved massive crunching with multiple algorithms. netflix settled on using the ~7.5% solution that involved only about ~2 choice algorithms blended. ie key tradeoff in algorithm complexity/implementation cost/effort vs payoff. so, it depends on your data if the gains are possible but it depends on effort/cost if its worth chasing small gains. therefore start with the simple approach & see if its "good enough" which a paper cant tell you. $\endgroup$ – vzn May 19 '12 at 15:27
  • $\begingroup$ @vzn From that article it seemed like their business model changed (from DVD to streaming) so that also influenced their decision not to implement the 10% version. $\endgroup$ – Joshua Herman May 21 '12 at 0:54
  • 1
    $\begingroup$ It's not clear to me what the question is, here. You know of some theoretical algorithms for their problem, but somehow they're not satisfactory: what would constitute a satisfactory solution? And your comparison of Yen (loopless shortest paths) vs my algorithm (much faster but generates paths that may contain loops) leaves me unsure whether you need the additional complexity of a loopless shortest path algorithm, or not. $\endgroup$ – David Eppstein May 21 '12 at 20:22
  • $\begingroup$ now the question seems contradictory because at 1st you ask for fastest sequential algorithm & then you point out flaws that the algorithms do not parallelize well. so which is it? $\endgroup$ – vzn May 22 '12 at 2:35
  • 1
    $\begingroup$ linked another closely related higher rated question & answered there. $\endgroup$ – vzn May 24 '12 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.