World Library  
Flag as Inappropriate
Email this Article

K shortest path routing

Article Id: WHEBN0037804593
Reproduction Date:

Title: K shortest path routing  
Author: World Heritage Encyclopedia
Language: English
Subject: Network theory, Yen's algorithm, Optical mesh network, Graph Theory
Collection: Computational Problems in Graph Theory, Graph Algorithms, Network Theory, Polynomial-Time Problems
Publisher: World Heritage Encyclopedia
Publication
Date:
 

K shortest path routing

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

Contents

  • History 1
  • Algorithm 2
    • First variant 2.1
    • Second variant 2.2
      • Paths are not required to be loopless 2.2.1
      • Loopless K shortest path routing algorithm 2.2.2
  • Some examples and description 3
    • Example #1 3.1
    • Example #2 3.2
  • Applications 4
  • Variations 5
  • Related problems 6
  • See also 7
  • Notes 8
  • References 9
  • External links 10

History

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

Important works on the K Shortest path problem:
Year of Publication Author Title
1971 Jin Y. Yen Finding the K Shortest Loopless Paths in a Network
1972 M. T. Ardon et al. A recursive algorithm for generating circuits and related subgraphs
1973 P. M. Camerini et al. The k shortest spanning trees of a graph
1975 K. Aihara An approach to enumerating elementary paths and cutsets by Gaussian elimination method
1976 T. D. Am et al. An algorithm for generating all the paths between two vertices in a digraph and its application
1988 Ravindra K. Ahuja et al. Faster algorithms for the shortest path problem
1989 S. Anily et al. Ranking the best binary trees
1990 Ravindra K. Ahuja et al. Faster algorithms for the shortest path problem
1993 El-Amin et al. An expert system for transmission line route selection
1997 David Eppstein Finding the k Shortest Paths
1977 Ingo Althöfer On the K-best mode in computer chess: measuring the similarity of move proposals
1999 Ingo Althöfer Decision Support Systems With Multiple Choice Structure
2011 Husain Aljazzar, Stefan Leue K*: A heuristic search algorithm for finding the k shortest paths

The BibTeX database contains more articles.

Algorithm

The Dijkstra algorithm can be generalized to find the K Shortest path.

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

There are mainly two variants of the K shortest path routing algorithm:

First variant

In the first variant, the paths are not required to be loopless (this is the simple one): David Eppstein's algorithm achieves the best running time complexity.[2]

Second variant

In the second variant, attributed to Jin Y. Yen, the paths are required to be loopless.[3] (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.

Eppstein's algorithm provides the best results.[2] Eppstein's model finds the K shortest paths (allowing cycles) connecting a given pair of vertices in a digraph, in time O(m+ nlogn + K).

Eppstein's algorithm uses a graph transformation technique.

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

Example #1

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

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" .

Applications

The K Shortest path routing is a good alternative for:

Variations

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.[2]
  • The second variation deals with simple paths. It is also called loopless K Shortest path routing problem and is attributed to J. Y. Yen [3]

Related problems

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

See also

Notes

  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 c Eppstein, D. (1998). "Finding the K shortest paths". SIAM J. Comput. 28 (2): 652–673.  
  3. ^ a b c Yen J. Y: “Finding the K-Shortest Loopless Paths in a Network”. Management Science 1971; 17:712–716
  4. ^ Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A 73 (2): 129–174.

References

  • 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.
  • 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/
  • BibTeX database: http://www.ics.uci.edu/~eppstein/bibs/kpath.bib
  • Computer Vision Laboratory: http://cvlab.epfl.ch/software/ksp/

External links

  • Implementation of Yen's algorithm
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.