K shortest path routing
It is sometimes crucial to have more than one path between two nodes in a given network. In the event there are additional constraints, other paths different from the shortest path can be computed. To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path. The K Shortest path routing algorithm is a generalization of the shortest path problem. The algorithm not only finds the shortest path, but also K other paths in order of increasing cost. K is the number of shortest paths to find. The problem can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop.
- 1 History
- 2 Algorithm
- 3 Some examples and description
- 4 Applications
- 5 Variations
- 6 Related problems
- 7 See also
- 8 Notes
- 9 References
- 10 External links
Since 1957 there have been many papers published on the K Shortest path routing algorithm problem. Most of the fundamental works on not just finding the single shortest path between a pair of nodes, but instead listing a sequence of the K shortest paths, were done between the 1960s and up to 2001. Since then, most of the recent research has been about the applications of the algorithm and its variants. In 2010, Michael Gunter et al. published a book on Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA.
Important works on the K Shortest path problem:
The BibTeX database contains more articles.
The Dijkstra algorithm can be generalized to find the K Shortest path.
There are mainly two variants of the K shortest path routing algorithm:
In the second variant, attributed to Jin Y. Yen, the paths are required to be loopless. (This restriction introduced another level of complexity.) Yen's algorithm is used where simple paths only are considered, whereas Eppstein's algorithm is used when non-simple paths are allowed (e.g., paths are allowed to revisit the same node multiple times).
Paths are not required to be loopless
In all that follows, m is the number of edges and n is the number of vertices.
This model can also find the K shortest paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn).
Loopless K shortest path routing algorithm
The best running time for this model is attributed to Jin. Y. Yen. Yen's algorithm finds the lengths of all shortest paths from a fixed node to all other nodes in an n-node non negative-distance network. This technique only requires 2n2 additions and n2 comparisons - which is less than other available algorithms require.
The running time complexity is O(Kn(m + n log n)). m represents the number of edges and n is the number of vertices.
Some examples and description
The following example makes use of Yen’s model to find the first K shortest paths between communicating end nodes. That is, it finds the first, second, third, etc. up to the Kth shortest path. More details can be found here. The code provided in this example attempts to solve the K Shortest path routing problem for a 15-nodes network containing a combination of unidirectional and bidirectional links:
Another example is the use of K Shortest algorithm to track multiple objects. The technique implements a multiple object tracker based on the K Shortest paths routing algorithm. A set of probabilistic occupancy maps is used as input. An object detector provides the input.
The complete details can be found at "Computer Vision Laboratory – CVLAB" .
The K Shortest path routing is a good alternative for:
- Geographic path planning
- Network routing, especially in optical mesh network where there are additional constraints that cannot be solved by using ordinary shortest path algorithms.
- Hypothesis generation in computational linguistics
- Sequence alignment and metabolic pathway finding in bioinformatics
- Multiple object tracking as described above
- Road Networks: road junctions are the nodes (vertices) and each edge (link) of the graph is associated with a road segment between two junctions.
There are two main variations of the K Shortest path routing algorithm as mentioned above. Other variations only fall in between these.
- In the first variation, loops are allowed, that is paths are allowed to revisit the same node multiple times. The following papers deal with this variation.
- The second variation deals with simple paths. It is also called loopless K Shortest path routing problem and is attributed to J. Y. Yen 
- Dijkstra's algorithm solves the single-source shortest path problems.
- The Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
- The breadth-first search algorithm is used when the search is only limited to two operations.
- The Floyd–Warshall algorithm solves all pairs shortest paths.
- Johnson's algorithm solves all pairs' shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
- Perturbation theory finds (at worst) the locally shortest path.
Cherkassky et al. provide more algorithms and associated evaluations.
- Shortest path problem
- Constrained shortest path routing
- Diverse Path Routing
- Shared Risk Group (SRG) and Shared Link Risk Group (SRLG)
- Michael Günther et al.: “Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA”. In: Int’l Workshop on Dynamic Aspects in Dependability Models for Fault-Tolerant Systems (DYADEM-FTS), ACM Press (2010) 13–18.
- Eppstein, D. (1998). "Finding the K shortest paths". SIAM J. Comput. 28 (2): 652–673. doi:10.1137/S0097539795290477.
- Yen J. Y: “Finding the K-Shortest Loopless Paths in a Network”. Management Science 1971; 17:712–716
- Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A 73 (2): 129–174.
- Michael Günther et al.:Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA. In: Int’l Workshop on Dynamic Aspects in Dependability Models for Fault-Tolerant Systems (DYADEM-FTS), ACM Press (2010) 13–18
- Yen J. Y:Finding the K-Shortest Loopless Paths in a Network. Management Science 1971; 17:712–716
- David Eppstein: Finding the k shortest paths. 35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154–165. Tech. Rep. 94–26, ICS, UCI, 1994. SIAM J. Computing 28(2):652–673, 1998.
- Multiple objects tracking technique using K-shortest path algorithm: http://cvlab.epfl.ch/software/ksp/
- BibTeX database: http://www.ics.uci.edu/~eppstein/bibs/kpath.bib
- Computer Vision Laboratory: http://cvlab.epfl.ch/software/ksp/