I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. The implementation is based on QuickGraph's Ranked Shortest Path implementation.

I have been trying to determine the complexity of Hoffman and Pavley's algorithm as well as QuickGraph's implementation, but without any luck -- so basically my question is if someone knows the complexity of the original method proposed by Hoffman and Pavley as well as the complexity of QuickGraph's implementation?

  • 3
    $\begingroup$ Seems David Eppstein algorithm is faster one : $O(m + n \log n + k \log k)$. If you really interested in best algorithm you can change your way. $\endgroup$ – user742 Nov 2 '12 at 9:12

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.