k shortest path routing

In 2010, Michael Günther et al. published a book on Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA.

[4] A solution was given by B. L. Fox in 1975 in which the k-shortest paths are determined in O(m + kn log n) asymptotic time complexity (using big O notation.

[5] In 1998, David Eppstein reported an approach that maintains an asymptotic complexity of O(m + n log n + k) by computing an implicit representation of the paths, each of which can be output in O(n) extra time.

The technique implements a multiple object tracker based on the k shortest paths routing algorithm.

Another use of k shortest paths algorithms is to design a transit network that enhances passengers' experience in public transportation systems.

Despite variations in parameters, the k shortest path algorithms finds the most optimal solutions that satisfies almost all user needs.

[9] The k shortest path routing is a good alternative for: Cherkassky et al.[10] provide more algorithms and associated evaluations.