Abstract
In the last 15 years, a good deal of effort has been devoted to the study of the shortest route problem. More than 200 publications are known but little has been reported concerning relative efficiencies. For a long time the Dijkstra method was considered the most efficient one. Programming work, using different data structures and implementation techniques for several algorithms, has shown that a variant of Moore's method seems to be most efficient for different types of graph structures.
The main objective of this paper is to show the strong relationship between an algorithm and its implementation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S.E. Dreyfus, “An appraisal of some shortest path algorithms”,Operations Research 17 (1969) 395–412.
E.F. Moore, “The shortest path through a maze”, in:Proceedings of an international symposium on the theory of switching, Part II, Apr. 2–5, 1957 (Harvard University Press, Cambridge, Ma., 1959).
U. Pape, “Netzwerkveränderungen und Korrektur kürzester Weglängen von einer Wurzelmenge zu allen anderen Knoten”, Technical University of Berlin, Department of Cybernetics, Tech. Rept. 73-17.
U. Pape, “Implementierung und Wirtschaftlichkeit von Moore-Algorithmen zur Bestimmung kürzester Weglängen in einem Netzwerk”, Technical University of Berlin, Department of Cybernetics, Tech. Rept. 73-06.
M. Pollack and W. Wiebenson, “Solutions of the shortest route problem — a review”,Operations Research 8 (1960) 224–230.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pape, U. Implementation and efficiency of Moore-algorithms for the shortest route problem. Mathematical Programming 7, 212–222 (1974). https://doi.org/10.1007/BF01585517
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585517