1
I Use This!
Activity Not Available
Analyzed 11 months ago. based on code collected 11 months ago.

Project Summary

The description of the original algorithm could be found in the paper, 'A New Implementation Of Yen's Ranking Loopless Paths Algorithm' (http://citeseer.ist.psu.edu/martins00new.html).

IntroductionYen’s algorithm is one of derivation algorithms for ranking the K shortest paths between a pair of nodes 1. It always searches the shortest paths in a “pseudo”-tree containing K shortest loopless paths. The very shortest one is obtained in the first place, and the second shortest path is always explored on the basis of the shortest paths that are shorter. In our paper, we exploit the implementation of Yen’s algorithm in 1. Compared with the straightforward implementation of Yen’s algorithm, the one present in 1 is proved to have a better performance in computational experiments, although the complexity of them are the same, O(Kn(m+nlogn)) in the worst case analysis.

ImplementationC++ language is used to implement Yen's algorithm, because of its high performance. In the implementation, we exploit the graph package in the boost c++ libraries 2, when calculating the shortest path in the graph. 2 provides the Fortran implementation of this algorithm. Java version is added. New C# version is added. ReferenceM. Pascoal and E. Martins. A new implementation of Yen’s ranking loopless paths algorithm. 4OR – Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003. http://www.mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html. Boost C++ Libraries, http://www.boost.org/. UpdateA fix on the comparator associated with Class QYDirectedPath is provided for the CPP implementation. Thanks a lot to timothyahahn. The implementation of top-k shortest path algorithm in C# by Vinh Bui (vinhqb@gmail.com) is added. Note that I don't test this code completely.

Tags

implementation yen graphtheory k-shortestpaths algorithm

In a Nutshell, k-shortest-paths...

This Project has No vulnerabilities Reported Against it

Did You Know...

  • ...
    Black Duck offers a free trial so you can discover if there are open source vulnerabilities in your code
  • ...
    you can embed statistics from Open Hub on your site
  • ...
    55% of companies leverage OSS for production infrastructure
  • ...
    check out hot projects on the Open Hub

Languages

Languages?height=75&width=75
C++
47%
Java
53%

30 Day Summary

Mar 17 2016 — Apr 16 2016

12 Month Summary

Apr 16 2015 — Apr 16 2016

Ratings

Be the first to rate this project
Click to add your rating
   Spinner
Review this Project!