k shortest path routing

The k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths (which may be longer than the shortest path).

Finding k shortest paths is possible by extending Dijkstra's algorithm or the Bellman-Ford algorithm.^{[citation needed]}

History

Since 1957, many papers have been published on the k shortest path routing problem. Most of the fundamental works were done between 1960s and 2001. Since then, most of the research has been on the problem's applications and its variants. 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.^[1]

Dijkstra's algorithm

Dijkstra's algorithm can be generalized to find the k shortest paths.^{[citation needed]}

Definitions: G(V, E): weighted directed graph, with set of vertices V and set of directed edges E, w(u, v): cost of directed edge from node u to node v (costs are non-negative). Links that do not satisfy constraints on the shortest path are removed from the graph s: the source node t: the destination node K: the number of shortest paths to find p_u: a path from s to u B is a heap data structure containing paths P: set of shortest paths from s to t count_u: number of shortest paths found to node u Algorithm: P =empty, count_u = 0, for all u in V insert path p_s = {s} into B with cost 0 while B is not empty and count_t < K: – let p_u be the shortest cost path in B with cost C – B = B − {p_u }, count_u = count_u + 1 – if u = t then P = P U {p_u} – if count_u ≤ K then for each vertex v adjacent to u: – let p_v be a new path with cost C + w(u, v) formed by concatenating edge (u, v) to path p_u – insert p_v into B return P

Yen's algorithm

Yen's algorithm^[2]^[3] is the most popular method to find single-source k shortest loopless paths for a graph with non-negative edge cost, it requires only 2n² additions and n² comparison, fewer than other available shortest path algorithms need. The running time complexity is pseudo-polynomial, being O(kn(m + n log n)) (where m and n represent the number of edges and vertices, respectively).^[2]^[3] In 2007, John Hershberger and Subhash Suri proposed a replacement paths algorithm, a more efficient implementation of Lawler's ^[4] and Yen's algorithm with O(n) improvement in time for a large number of graphs, but not all of them (therefore not changing the asymptotic bound of Yen's algorithm).^[5]

There is a paltry variation for finding k shortest paths with loops. However, there is little demand for finding k shortest paths to have repeated vertices (loops).

Some examples and description

Example 1

The following example makes use of Yen’s model to find k shortest paths between communicating end nodes. That is, it finds a shortest path, second shortest path, etc. up to the K^th 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:

Example 2

Another example is the use of k shortest paths 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".

Example 3

Another use of k shortest paths algorithms is to design a transit network that enhances passengers' experience in public transportation systems. Such an example of a transit network can be constructed by putting traveling time under consideration. In addition to traveling time, other conditions may be taken depending upon economical and geographical limitations. Despite variations in parameters, the k shortest path algorithms finds the most optimal solutions that satisfies almost all user needs. Such applications of k shortest path algorithms are becoming common, recently Xu, He, Song, and Chaudry (2012) studied the k shortest path problems in transit network systems.^[6]

Applications

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.

Notes

^ Günther, Michael; Schuster, Johann; Siegle, Markus (2010-04-27). "Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA". Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA. ACM. pp. 13–18. doi:10.1145/1772630.1772635. ISBN 978-1-60558-916-9.
^ ^a ^b Cite error: The named reference Yen was invoked but never defined (see the help page).
^ ^a ^b Cite error: The named reference Bouillet was invoked but never defined (see the help page).
^ Lawler, Eugene L. (1972-03-01). "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem". Management Science. 18 (7): 401–405. doi:10.1287/mnsc.18.7.401. ISSN 0025-1909.
^ Hershberger, John; Maxel, Matthew; Suri, Subhash (2007). "Finding the k Shortest Simple Paths: A New Algorithm and its Implementation" (PDF). ACM Transactions on Algorithms. 3 (4). Article 45 (19 pages). doi:10.1145/1290672.1290682. S2CID 10703503.
^ Xu, Wangtu; He, Shiwei; Song, Rui; Chaudhry, Sohail S. (2012). "Finding the k shortest paths in a schedule-based transit network". Computers & Operations Research. 39 (8): 1812–1826. doi:10.1016/j.cor.2010.02.005. S2CID 29232689.
^ Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: Theory and experimental evaluation". Mathematical Programming. 73 (2): 129–174. doi:10.1007/BF02592101. ISSN 0025-5610. S2CID 414427.

External links

Implementation of Yen's algorithm
Implementation of Yen's and fastest k shortest simple paths algorithms
http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/#more-2432
Multiple objects tracking technique using K-shortest path algorithm: http://cvlab.epfl.ch/software/ksp/
Computer Vision Laboratory: http://cvlab.epfl.ch/software/ksp/

[1] Günther, Michael; Schuster, Johann; Siegle, Markus (2010-04-27). "Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA". Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA. ACM. pp. 13–18. doi:10.1145/1772630.1772635. ISBN 978-1-60558-916-9.

[Yen-2] Cite error: The named reference Yen was invoked but never defined (see the help page).

[Bouillet-3] Cite error: The named reference Bouillet was invoked but never defined (see the help page).

[4] Lawler, Eugene L. (1972-03-01). "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem". Management Science. 18 (7): 401–405. doi:10.1287/mnsc.18.7.401. ISSN 0025-1909.

[5] Hershberger, John; Maxel, Matthew; Suri, Subhash (2007). "Finding the k Shortest Simple Paths: A New Algorithm and its Implementation" (PDF). ACM Transactions on Algorithms. 3 (4). Article 45 (19 pages). doi:10.1145/1290672.1290682. S2CID 10703503.

[6] Xu, Wangtu; He, Shiwei; Song, Rui; Chaudhry, Sohail S. (2012). "Finding the k shortest paths in a schedule-based transit network". Computers & Operations Research. 39 (8): 1812–1826. doi:10.1016/j.cor.2010.02.005. S2CID 29232689.

[7] Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: Theory and experimental evaluation". Mathematical Programming. 73 (2): 129–174. doi:10.1007/BF02592101. ISSN 0025-5610. S2CID 414427.

[1]

[2]

[3]

[4]

[5]

[6]

[7]