k shortest path routing

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The k shortest path routing algorithm is an extension algorithm of the shortest path routing algorithm in a given network.

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 − 1 other paths in non-decreasing order of 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.

History[edit]

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 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]

Algorithm[edit]

The Dijkstra algorithm can be generalized to find the k shortest paths.

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
  • Pu: a path from s to u
  • B is a heap data structure containing paths
  • P: set of shortest paths from s to t
  • countu: number of shortest paths found to node u

Algorithm:

P =empty,
countu = 0, for all u in V
insert path Ps = {s} into B with cost 0
while B is not empty and countt < K:
– let Pu be the shortest cost path in B with cost C
B = B{Pu }, countu = countu + 1
– if u = t then P = P U {Pu}
– if countuK then
  • for each vertex v adjacent to u:
– let Pv be a new path with cost C + w(u, v) formed by concatenating edge (u, v) to path Pu
– insert Pv into B
return P

Variations[edit]

There are two main variations of the k shortest path routing algorithm, though others falling between these exist. In the first, paths in which nodes are visited more than once are allowed, creating loops. In the second, paths are required to be simple and loopless. The first is solvable using Eppstein's algorithm[2] and the latter by Yen's algorithm and is also known as the loopless k shortest path routing problem.[3][4]

First variant[edit]

In the first variant, the problem is simplified by not requiring paths to be loopless.[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.[2][4] In 2007, John Hershberger and Subhash Suri proposed a replacement paths algorithm, a more efficient implementation of Eppstein's algorithm with O(n) improvement in time.[6] In 2015, Akuba et al. devised an indexing method as a significantly faster alternative for Eppstein's algorithm, in which a data structure called an index is constructed from a graph and then top-k distances between arbitrary pairs of vertices can be rapidly obtained.[7]

Second variant[edit]

The second variant adds a restriction that paths are required to be loopless, adding an additional level of complexity,[4] and was solved by Jin Y. Yen.[3] Yen's algorithm[4] finds the lengths of all shortest paths from a fixed node to all other nodes in an n-node non negative-distance network, a technique requiring only 2n2 additions and n2 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).[3][4]

Some examples and description[edit]

Example #1[edit]

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:

15-node network containing a combination of bi-directional and uni-directional links

Example #2[edit]

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[edit]

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

Applications[edit]

The k shortest path routing is a good alternative for:

Related problems[edit]

Cherkassky et al.[9] provide more algorithms and associated evaluations.

See also[edit]

Notes[edit]

  1. ^ 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.
  2. ^ a b Eppstein, David (1998). "Finding the k Shortest Paths" (PDF). SIAM J. Comput. 28 (2): 652–673. doi:10.1137/S0097539795290477.
  3. ^ a b c Yen, J. Y. (1971). "Finding the k-Shortest Loopless Paths in a Network". Management Science. 1 7 (11): 712–716. doi:10.1287/mnsc.17.11.712..
  4. ^ a b c d e f Bouillet, Eric; Ellinas, Georgios; Labourdette, Jean-Francois; Ramamurthy, Ramu (2007). "Path Routing – Part 2: Heuristics". Path Routing in Mesh Optical Networks. John Wiley & Sons. pp. 125–138. ISBN 9780470015650.
  5. ^ Fox, B. L. (1975). "Kth shortest paths and applications to the probabilistic networks". ORSA/TIMS Joint National Meeting. 23: B263. CiNii National Article ID: 10012857200.
  6. ^ 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.
  7. ^ Akuba, Takuya; Hayashi, Takanori; Nori, Nozomi; Iwata, Yoichi; Yoshida, Yuichi (January 2015). "Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling". Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Austin, TX: Association for the Advancement of Artificial Intelligence. pp. 2–8.
  8. ^ Xu, W., He, S., Song, R., & Chaudhry, 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
  9. ^ Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A 73 (2): 129–174.

External links[edit]