Algorithm 562: Shortest Path Lengths [H]
Uwe Pape · ACM Transactions on Mathematical Software · 1980
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 [5,6].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.The main idea of the given algorithm centers around the "status" of a newfound successor node j.Ifj has not yet been reached by the process, it is entered at the end of the successor list; if it is currently in the list, no new entry is made, but if it has already been processed and removed from the list, it is entered at the top of the list so that it will be processed next.The current status of each node is recorded by the values of the list which are stored as linked deque (doubleended queue).The steps involved are as follows: top element of the deque := ]; mj := o% mjj := O; while deque ~ ~ do begin t := top element of the deque; remove top element; for all successors k of t do begin mjk := mj, + d,k if mjk < rnfi then begin mfi := mjk; wjk := t;