|Contact:||daniel at georepublic.de|
Yen’s algorithm is one of derivation algorithms for ranking the K shortest paths between a pair of nodes . 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 . Compared with the straightforward implementation of Yen’s algorithm, the one present in  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.
 M. 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.
The source above provides an implementation of K-Shortest Path Algorithm written in C++, available under Apache License 2.0
If possible adapt this implementation to make it available as pgRouting function.
Are not expected
No vote yet.