A Shortest Path Algorithm for Edge-Sparse Graphs
- 1 January 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (1), 50-57
- https://doi.org/10.1145/321921.321927
Abstract
An algorithm ( FLOW ) for finding the shortest distance from a given node S to each node X of a directed graph with nonnegative integer arc lengths less than or equal to WM is presented. FLOW is compared with its best-known competitor, that of Dijkstra and Yen ( DFLO ). The new algorithm is shown to execute in time of order max ( V, E, D ), where D is the maximum distance computed in a graph with E edges and V nodes. By counting the number of operands fetched during execution of FLOW and DFLO , an estimate of the running time of each is obtained. This estimate shows that FLOW should execute faster than DFLO when E / V 2 = α < .2875, and V ≥ 22 WM / β + 5/ β + 7.04, where β = 23 - 80 α . FLOW also will solve the all-pairs shortest distance problem, requiring time O ( V * max( V, E, D )) for the solution.Keywords
This publication has 6 references indexed in Scilit:
- Two languages for estimating program efficiencyCommunications of the ACM, 1974
- Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½
N
3
Additions and
N
3
ComparisonsJournal of the ACM, 1972
- An Appraisal of Some Shortest-Path AlgorithmsOperations Research, 1969
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961
- Solutions of the Shortest-Route Problem—A ReviewOperations Research, 1960
- A note on two problems in connexion with graphsNumerische Mathematik, 1959