Computing the N Best Loopless Paths in a Network

Statement of the problem. Consider a network consisting of points, or nodes, and of directed arcs, or links, joining some pairs of nodes. If A and B are any two nodes, the network may contain a link AB, with initial node A and terminal node B, or a link BA, or both, or neither. Suppose that to each link AB is assigned a positive number L(AB), the length, or value, of the link. If AB and BA both exist, it is not required that L(BA) = L(AB). A path (or chain) from a node A to a node B of the network is a finite sequence of links of the form (PoP1, P1P2, ... , PnlPn), where Po = A, Pn = B, n is a positive integer, and the nodes (called the nodes of the path) are not necessarily distinct. The length of a path p, L(p), is defined to be the sum of the lengths of its links. The empty path (from A to A, for any node A) is an empty set of links, and its length is zero. A path is loopless, or proper, if it does not include closed loops, i.e., if its nodes are all distinct. In Fig. 1, path p is proper and path p' is not proper. Assume now (1) that the number of nodes is finite, (2) that for any two nodes A, B, there is a path from A to B. Thus, we have a finite, connected graph. Given nodes 0 and Z of the graph, and a positive integer N, the problem of the N best loopless paths is that of finding, from among all the proper paths from 0 to Z, a set S of N shortest paths, i.e. such that if p is a path in S and q is a proper path from 0 to Z not in S, then L(p) _ L(q). Hoffman and Pavley [1] have described a practical method used in finding a set of N best paths in a network, but did not show clearly how to modify the procedure to avoid paths with loops. (See the discussion in [2].) The purpose of the present paper is to offer a modified and extended version of that method, which does restrict the solution to proper paths.