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] 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 107609, 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 214405, 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