# What is the complexity of Hoffman and Pavley's Nth best path algorithm?

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?

• 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. – user742 Nov 2 '12 at 9:12