The concern of this paper is a generalization of theshortest path problem, in which not only one but several short pathsmust be produced. More precisely, the k-shortest path problem is to list thek paths connecting a given source-destination pair inthe digraph with minimum total length. The proposed algorithms output animplicit representation of these k shortest paths (allowing cycles) connecting a givenpair of vertices in a digraph with n vertices and m edges in time O(m+nlogn+k). Furthermore, the algorithms allow us to find thek shortest paths from a given source in a digraph toeach other vertex in time O(m+nlogn+kn). The similar problem of finding paths shorter than agiven length, with the same time bounds, is considered. Shortest pathcomputation has numerous applications; the author details itsapplications to dynamic programming problems including the optimization0–1 knapsack problem, the sequence alignment or edit distanceproblem, the problem of inscribed polygons (which arises in computergraphics), and genealogical relations. A list of open problems concludesthis interesting paper.