RFC 04: [done] Implementation of “k-shortest path” algorithm

Date:

2010/11/22

Author:

Daniel Kastl

Contact:

daniel at georepublic.de

Last Edited:

2013/06/09

Status:

Implemented (v2.0.0)

Overview

Yen’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.

[1] 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.

[Source: https://code.google.com/p/k-shortest-paths/]

Implementation Details

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.

Backwards Compatibilty Issues

Are not expected

Documentation

Required.

Ticket ID

Not assigned.

Voting History

No vote yet.