Algorithm 562: Shortest Path Lengths [H]

Abstract

Key Words and Phrases CR Categor)es' 5 32 Language Fortran IV shortest path, shortest route problem DESCRIPTION This algorithm finds the shortest path lengths from a specific node to all other nodes in a network. It is a modification of Moore's algorithm [4], originally due to d'Esopo as reported by Pollack and Wiebenson [7] and refined by Pape The algorithm does not determine the shortest paths. If a shortest path is to be determined, this algorithm may be combined with any algorithm that traces the shortest path from the root node to any other node from the list of predecessors of nodes. As the calculation of the path lengths is the most rime-consuming part of the whole process, we confine our attention to this problem.