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] 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

American Mathematical Society