An algorithm for finding shortest routes from all source nodes to a given destination in general networks

Author:
Jin Y. Yen

Journal:
Quart. Appl. Math. **27** (1970), 526-530

DOI:
https://doi.org/10.1090/qam/253822

MathSciNet review:
253822

Full-text PDF Free Access

Abstract | References | Additional Information

Abstract: This paper presents an algorithm for finding all shortest routes from all nodes to a given destination in -node general networks (in which the distances of arcs can be negative). If no negative loop exists, the algorithm requires , additions and comparisons. The existence of a negative loop, should one exist, is detected after additions and comparisons.

**[1]**R. E. Bellman,*On a routing problem*, Quart. Appl. Math.**16**, 87-90 (1958) MR**0102435****[2]**G. B. Dantzig, W. O. Blattner and M. R. Rao,*All shortest routes from a fixed origin in a graph*, Technical Report No. 66-2, Operations Research House, Stanford University, Nov. 1966 MR**0221980****[3]**G. B. Dantzig,*All shortest routes in a graph*, Technical Report No. 66-3, Operations Research House, Stanford University, Nov. 1966 MR**0221981****[4]**E. W. Dijkstra,*A Note on two problems in connexion with graphs*, Numer. Math.**1**, 269-271 (1959) MR**0107609****[5]**S. E. Dreyfus,*An appraisal of some shortest path algorithms*, Memorandum RM-5433-PR, RAND Corp., Oct. 1967**[6]**-,*An appraisal of some shortest path algorithms (revised)*, Memorandum RM-5433-1-PR, RAND Corp., Sept. 1968**[7]**R. W. Floyd,*Algorithm*97,*shortest path*, Comm. ACM (6)**5**, 345 (1962)**[8]**L. R. Ford, Jr.,*Network flow theory*, RAND Corp., P-923, Aug. 1956**[9]**T. C. Hu,*Revised matrix algorithms for shortest paths*, SIAM J. Appl. Math. (1)**15**, 207-218 (1967) MR**0214405****[10]**T. C. Hu,*A decomposition algorithm for shortest paths in a network*, Operations Res. (1)**16**, 91-102 (1968)**[11]**E. F. Moore,*The shortest path through a maze*, Proc. Internat. Sympos. on the Theory of Switching, II, April, 1957**[12]**J. D. Murchland,*A new method for finding all elementary paths in a complete directed graph*, London School of Economics, Report LSE-TNT-22, 1965**[13]**A. C. Parikh,*Some theorems and algorithms for finding optimal paths over graphs with engineering applications*, Ph.D. thesis, Purdue University, 1960**[14]**J. Y. Yen,*Some algorithms for finding the shortest routes through the general networks*, Paper presented at the SIAM 2nd Internat. Conf. on Computation Methods on Optimization Problems, San Remo, Italy, Sept. 1968 MR**0272549****[15]**-,*A matrix algorithm for solving all shortest routes from a fixed origin in the non-negative networks*, Paper presented at the TIMS 15th Internat. Meeting, Cleveland, Ohio, Sept. 1968

Additional Information

DOI:
https://doi.org/10.1090/qam/253822

Article copyright:
© Copyright 1970
American Mathematical Society