Iterative methods for determining the k shortest paths in a network

Abstract

Abstract This paper presents and develops an algebraic structure for determining the k shortest paths from a given node to all other nodes of a network. Three new methods for calculating such k shortest path information are examined and compared. These methods are based on a fairly strong analogy which exists between the solution of such network problems and traditional techniques for solving linear equations. On the basis of both theoretical and computational evidence, one of the three methods is seen to offer an extremely effective procedure for finding the k shortest paths from a given node in a network.