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

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]**Richard Bellman,*On a routing problem*, Quart. Appl. Math.**16**(1958), 87–90. MR**0102435**, https://doi.org/10.1090/S0033-569X-1958-0102435-2**[2]**G. B. Dantzig, W. O. Blattner, and M. R. Rao,*All shortest routes from a fixed origin in a graph*, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 85–90 (English, with French summary). MR**0221980****[3]**G. B. Dantzig,*All shortest routes in a graph*, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 91–92 (English, with French summary). MR**0221981****[4]**E. W. Dijkstra,*A note on two problems in connexion with graphs*, Numer. Math.**1**(1959), 269–271. MR**0107609**, https://doi.org/10.1007/BF01386390**[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.**15**(1967), 207–218. MR**0214405**, https://doi.org/10.1137/0115017**[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]**Jin Y. Yen,*Some algorithms for finding the shortest routes through the general networks*, Computing Methods in Optimization Problems, 2 (Proc. Conf., San Remo, 1968), Academic Press, New York, 1969, pp. 377–388. 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