Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



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 $ N$-node general networks (in which the distances of arcs can be negative). If no negative loop exists, the algorithm requires $ \frac{1}{2}M\left( {N - 1} \right) \\ \left( {N - 2} \right),1 < MN - 1$, additions and comparisons. The existence of a negative loop, should one exist, is detected after $ \frac{1}{2}N\left( {N - 1} \right)\left( {N - 2} \right)$ additions and comparisons.

References [Enhancements On Off] (What's this?)

  • [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