Abstract
The first image that comes to mind when the word ‘network’ is mentioned is a traffic network, whether it be road or air traffic. Most of us are familiar with such networks since one rarely travels from one location to another without consulting a ‘map’, which is, in our terminology, a ‘network’.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References to Chapter 1
Akkanad, M. I. and E. Turban, “Some Comments on the Traveling Salesman Problem”, Oper. Res., Vol. 17, No. 3, May-June 1969.
Bellman, R. and R. Kalaba, “On the kth Best Policies”, Journal of SIAM, Vol. 8, No. 4, Dec. 1960.
Bellmore, M. and G. L. Nemhauser, “The Traveling Salesman Problem: A Survey”, Oper. Res., Vol. 16, No. 3, May-June 1968.
Busacker, R. G. and T. L. Saaty, “Finite Graphs and Networks”, McGraw-Hill, 1965.
Charnes, A. and W. W. Cooper, “A Network Interpretation and a Directed Subdual Algorithm for Critical Path Scheduling”, Jour. of Ind. Eng., Vol. 13, No. 4, 1962.
Clarke, S., A. Kirkonian and J. Rausen, “Computing the n Best Loopless Paths in a Network”, Journal of SIAM, Vol. II, No. 4, Dec. 1963, pp.1096–1102.
Dantzig, G. B., “On the Shortest Route Through a Network”, Mgt. Sc., Vol. 6, No. 2, Jan. 1960, pp. 187–190.
Dantzig, G. B., “Linear Programming and Extensions”, Princeton Univ. Press, 1963.
Dijkstra, E. W., “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, Vol. 1, pp. 269–271, 1959.
Dreyfus, S. E., “An Appraisal of Some Shortest-Path Algorithms”, Oper. Res., Vol. 17, No. 3, May-June 1969.
Elmaghraby, S. E., “The Design of Production Systems”, Reinhold, 1966, pp. 98–140.
Fan, L. T. and C. W. Wang, “The Discrete Maximum Principle”, Wiley, 1964.
Farbey, B. A., A. H. Land and J. D. Murchland, “The Cascade Algorithm for Finding the Minimum Distances on a Graph”, Transport Network Theory Unit, London School of Economics, Nov. 1964.
Floyd, R. W., “Algorithm 97, Shortest Path”, Comm. ACM, Vol. 5, p.345, 1962.
Ford, L. R. and D. R. Fulkerson, “Flows in Networks”, Princeton Univ. Press, 1962.
Geoffrion, A. M., “An Improved Implicit Enumeration Approach for Integer Programming”, Oper. Res., Vol. 17, No. 3, May-June 1969.
Hardgrave, W. W. and G. L. Nemhauser, “On the Relation Between the Traveling Salesman and the Longest Path Problems”, Oper. Res., Vol. 10, No. 5, Sept.-Oct. 1962.
Hoffman, W. and R. Pavley, “A Method for the Solution of the nth Best Path Problem”, Jour. Assoc. Comput. Mach., Vol. 6, 1959, pp. 506–514.
Hu, T. C., “Revised Matrix Algorithms for Shortest Paths”, IBM Research Center, Research Paper RC-1478, Sept. 1965.
Hu, T. C., “A Decomposition Algorithm for Shortest Paths in a Network”, IBM Watson Research Center, Yorktown Heights, N. Y., Feb. 1966.
Kruskal, J. B., Jr., “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proc. Amer. Math. Soc., Vol. 7, 1956, pp. 48–50.
Minty, G. J., “A Comment on the Shortest-Route Problem”, Oper. Res. Vol. 5, No. 5, Oct. 1957, p. 724.
Moore, E. F., “The Shortest Path Through a Maze”, Proc. Intl. Symp. on The Theory of Switching, Part II, April 2–5, 1957. The Annals of the Computation Laboratory of Harvard Univ., Vol. 30, Harvard Univ. Press, 1959.
Murchland, J. D., “A New Method for Finding All Elementary Paths in a Complete Directed Graph”, LSE-TNT-22, London School of Economics, Oct. 1965.
Parikh, S. C., and W. S. Jewell, “Decomposition of Project Networks”, Mgt. Sc, Vol. 11, No. 3, Jan. 1965, pp. 438–443.
Pierce, J. F., Jr. and D. J. Hatfield, “Production Sequencing by Combinatorial Programming,” Ch. 17 of Operations Research and Management Information Systems, Ed. by J. F. Pierce, Jr., TAPPI, 1966.
Pollack, M., “Solutions of the kth Best Route Through a Network — A Review”, Journ. Math. Analysis and Appl., Vol. 3, No. 3, Dec. 1961, pp. 547–659.
Pollack, M., “The kth Best Route Through a Network”, Oper. Res.,Vol. 9, No. 4, July-August 1961, pp. 578–580.
Pollack, M., and W. Wiebenson, “Solutions of the Shortest Route Problem-A Review”, Oper. Res., Vol. 8, No. 2, March-April 1960, pp. 224–230.
Prim, R. C., “Shortest Connection Networks and Some Generalizations”, Bell System Technical Jour., Vol. 36, 1957, pp. 1389–1401.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1970 Springer-Verlag Berlin · Heidelberg
About this chapter
Cite this chapter
Elmaghraby, S.E. (1970). The Shortest Path Problems. In: Some Network Models in Management Science. Lecture Notes in Economics and Mathematical Systems, vol 29. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-80558-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-80558-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-04952-4
Online ISBN: 978-3-642-80558-5
eBook Packages: Springer Book Archive