A dual simplex algorithm for finding all shortest paths

Publisher Website
Google Scholar
Abstract
We present an adaptation of the dual simplex algorithm, for computing all shortest paths on a network. Given a shortest path arborescence rooted at node r, the change of root to a new origin s, renders the arborescence rooted at r dual feasible and primal infeasible for the new problem. The adaptation of the dual simplex algorithm to compute the shortest paths from node s results in an algorithm which has the flavor of a label‐setting method. It generally does not require the examination of all the nodes of the network. We report some computational results with the method which indicate that it is at least as efficient as successive applications of a label‐setting or a label‐correcting shortest path algorithm.