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.

- Richard Bellman,
*On a routing problem*, Quart. Appl. Math. **16** (1958), 87–90. MR **102435**, DOI https://doi.org/10.1090/S0033-569X-1958-0102435-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**
- 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**
- E. W. Dijkstra,
*A note on two problems in connexion with graphs*, Numer. Math. **1** (1959), 269–271. MR **107609**, DOI https://doi.org/10.1007/BF01386390
S. E. Dreyfus, *An appraisal of some shortest path algorithms*, Memorandum RM-5433-PR, RAND Corp., Oct. 1967
---, *An appraisal of some shortest path algorithms (revised)*, Memorandum RM-5433-1-PR, RAND Corp., Sept. 1968
R. W. Floyd, *Algorithm* 97, *shortest path*, Comm. ACM (6) **5**, 345 (1962)
L. R. Ford, Jr., *Network flow theory*, RAND Corp., P–923, Aug. 1956
- T. C. Hu,
*Revised matrix algorithms for shortest paths*, SIAM J. Appl. Math. **15** (1967), 207–218. MR **214405**, DOI https://doi.org/10.1137/0115017
T. C. Hu, *A decomposition algorithm for shortest paths in a network*, Operations Res. (1) **16**, 91–102 (1968)
E. F. Moore, *The shortest path through a maze*, Proc. Internat. Sympos. on the Theory of Switching, II, April, 1957
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
A. C. Parikh, *Some theorems and algorithms for finding optimal paths over graphs with engineering applications*, Ph.D. thesis, Purdue University, 1960
- 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**
---, *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

R. E. Bellman, *On a routing problem*, Quart. Appl. Math. **16**, 87–90 (1958)
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
G. B. Dantzig, *All shortest routes in a graph*, Technical Report No. 66–3, Operations Research House, Stanford University, Nov. 1966
E. W. Dijkstra, *A Note on two problems in connexion with graphs*, Numer. Math. **1**, 269–271 (1959)
S. E. Dreyfus, *An appraisal of some shortest path algorithms*, Memorandum RM-5433-PR, RAND Corp., Oct. 1967
---, *An appraisal of some shortest path algorithms (revised)*, Memorandum RM-5433-1-PR, RAND Corp., Sept. 1968
R. W. Floyd, *Algorithm* 97, *shortest path*, Comm. ACM (6) **5**, 345 (1962)
L. R. Ford, Jr., *Network flow theory*, RAND Corp., P–923, Aug. 1956
T. C. Hu, *Revised matrix algorithms for shortest paths*, SIAM J. Appl. Math. (1) **15**, 207–218 (1967)
T. C. Hu, *A decomposition algorithm for shortest paths in a network*, Operations Res. (1) **16**, 91–102 (1968)
E. F. Moore, *The shortest path through a maze*, Proc. Internat. Sympos. on the Theory of Switching, II, April, 1957
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
A. C. Parikh, *Some theorems and algorithms for finding optimal paths over graphs with engineering applications*, Ph.D. thesis, Purdue University, 1960
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
---, *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

Article copyright:
© Copyright 1970
American Mathematical Society