(classic problem)
Definition: The problem of finding the kth shortest path from one vertex in a graph to another vertex. Variants may require that paths are edge- or vertex-disjoint, that is sharing no edges or vertices. "Shortest" may be least number of edges, least total weight, etc.
Specialization (... is a kind of me.)
shortest path.
Author: PEB
The optimal problem page with definitions, links to basic concepts, variants, and algorithms.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 19 September 2005.
HTML page formatted Mon Sep 11 09:46:04 2006.
Cite this as:
Paul E. Black, "kth shortest path", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 19 September 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/kthShortestPath.html