NIST

kth shortest path

(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


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 10 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "kth shortest path", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/kthShortestPath.html