Jump to content

K shortest path routing

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ccalmen (talk | contribs) at 20:48, 1 December 2012 (←Created page with '{{subst:AFC submission/draftnew}} <!--- Important, do not remove this line before article has been created. ---> Sometimes it is crucial to have more than one pa...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Sometimes it is crucial to have more than one path between two nodes in a given network. In the event there are additional constraints, we could use a path different from the shortest one to achieve our goal. To find the shortest path we 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 an extension algorithm of the shortest-path routing algorithm in a network. It is a generalization of the shortest path problem. K-shortest path routing algorithms not only find the shortest path, but also K other paths in order of increasing cost. K is the number of shortest paths to find. The constraints that can be imposed on the shortest path can be the following: Minimum cost with bounded total latency, Minimum cost with additive link metrics such as delay, Minimum cost with minimum bandwidth, Minimum cost and including/excluding certain nodes (also called [[ http://www.cs.odu.edu/~toida/nerzic/content/digraph/definition.html%7Cvertices]]) or certain links (also referred to as edges). Moreover we can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop. This last constraint is the most relevant in mesh optical network.

HISTORY

They are many papers on K-Shortest path problem going back as far as 1957. The collection of bibliographies and scientific literature in computer science website, which address is http://liinwww.ira.uka.de/bibliography/Theory/k-path.html#browse gives a visual statistic on the K shortest path research papers until 2001. The following figure is a Bibliographic Statistics that lists papers studying a generalization of the shortest path problem:

File:DistributionOfPublicationDates
Bibliography Of Distribution Of Publication Dates

Scientists are still exploring the K-Shortest path problem. One of the most recent works is by Michael Gunter et al. who published a book in 2010 on some “Symbolic calculation of k-shortest paths and related measures with the stochastic process algebra tool CASPA”.[1] But as stated on the Bibliographies on algorithms for k-shortest paths website 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 60’s and up to 2001. Since then, most of the papers are about the applications of the algorithm and its variants. The article by J. Y.Yen, “FINDING THE K SHORTEST LOOPLESS PATHS IN A NETWORK*-1971” [2] is the most referred article on the subject. Here are some of the most important research papers 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 Alok Aggarwal et al. Finding a minimum weight K-link path in graphs with Monge property and applications
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

For more references, visit the following link: http://www.ics.uci.edu/~eppstein/bibs/kpath.bib David Eppstein and Ingo Althöfer have done a lot of research on the K Shortest path problem.

ALGORITHM

Dijkstra algorithm can be generalized to find the K-Shortest path[3].

Note: To better understand the concept of Vertex, Vertices and edges, the reader is encouraged to visit the following http://www.cs.odu.edu/~toida/nerzic/content/digraph/definition.html.
Definitions:
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,
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 countu K 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

They are mainly two variants of the K-Shortest path algorithm:

First Variant

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

Second Variant

In the second variant, attributed to Jin Y. Yen, the paths are required to be loopless[5] (this restriction introduced another level of complexity).

To make it easy to understand Yen's algorithm is used in the case where simple paths only are considered, whereas Eppstein algorithm is 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

Eppstein algorithm provides the best results. The full article can be found here[6]. Eppstein model finds the K shortest paths (allowing cycles) connecting a given pair of vertices in a digraph, in time O(m + nlogn + K).

Breadth first search (BFS) [7] technique is applied. 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 + nlogn + kn).

m is the number of edges and n is the number of vertices.

Loopless K-Shortest path algorithm

The best running time for this model is attributed to Jin. Y. Yen and the full article can be found here[8]. 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 what other available algorithms required. An implementation of Yen’s algorithm can be found here[9].

The running time complexity is O(K n(m + nlogn)).

SOME EXAMPLES AND DESCRIPTION

Example #1

The following example makes use of the 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. Please follow this link ( http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/#more-2432) for more details. The code provided in this example attempts to solve the K Shortest path problem for a 15-nodes network containing a combination of unidirectional and bidirectional links:

File:15-nodes-network
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 algorithm. A set of probabilistic occupancy maps is used as input. An object detector provides the input. The complete details can be found here.

APPLICATIONS

The K Shortest is a good alternative for:

VARIATIONS

They are two main variations of the K Shortest path 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 [10].
  • The second variation deals with simple paths. It is also called loopless K-Shortest path problem and is attributed to J. Y. Yen [11]

Cherkassky et al.[12] 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. ^ Yen J. Y: “Finding the K-Shortest Loopless Paths in a Network”. Management Science 1971; 17:712-716
  3. ^ Eric Bouillet, Georgios Ellinas, Jean-Francois Labourdette, Ramu Ramamurthy: “Path Routing in Mesh Optical Networks”; Wiley-Interscience; 1st edition (November 20, 2007): P132-133
  4. ^ D. 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.
  5. ^ Yen J. Y: “Finding the K-Shortest Loopless Paths in a Network”. Management Science 1971; 17:712-716
  6. ^ D. 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.
  7. ^ Breath First Search Algorithm: http://en.wikipedia.org/wiki/Breadth-first_search
  8. ^ J. Y. Yen article on loopless K-Shortest path algorithm: http://adrian.idv.hk/lib/exe/fetch.php/paper/y71-shortestpath.pdf
  9. ^ An implementation of Yen’s algorithm: http://code.google.com/p/k-shortest-paths/
  10. ^ D. 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.
  11. ^ Yen J. Y: “Finding the K-Shortest Loopless Paths in a Network”. Management Science 1971; 17:712-716
  12. ^ 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

Retrieved from "https://en.wikipedia.org/w/index.php?title=K_shortest_path_routing&oldid=525916761"