The k Shortest Paths Problem

: The shortest path problem is a classical network programming problem that has been extensively studied. The problem of determining not only the shortest path, but also listing the K shortest paths (for a given integer K > 1) is also a classical one but has not been studied so intensively, despite its obvious practical interest. Two di(cid:11)erent types of problems are usually considered: the unconstrained and the constrained K shortest paths problem. While in the former no restriction is considered in the de(cid:12)nition of a path, in the constrained K shortest paths problem all the paths have to satisfy some condition { for example, to be loopless. In this paper we are concerned with the unconstrained ranking shortest paths problem. In the (cid:12)rst part the problem is viewed as a generalization of the classical shortest path problem; conditions for (cid:12)niteness and for the optimality principle being satis(cid:12)ed are studied as well as labeling shortest path algorithms are generalized. In the second part the problem is viewed under a di(cid:11)erent perspective; new algorithms are proposed which compute a super set of the set of the K shortest paths.