Dijkstra's algorithm revisited: the dynamic programming connexion

• Autorzy: Sniedovich M.
• Języki publikacji: EN

Abstrakty

EN

Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic programming should be (at least) alluded to in a proper exposition/teaching of the algorithm.

Słowa kluczowe

EN

Dijkstra's algorithm; dynamic programming; greedy algorithm; principle of optimality; successive approximation; operations research; computer science

PL

programowanie dynamiczne; badania operacyjne

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 599--620
• Opis fizyczny: Bibliogr. 29 poz., rys.

Twórcy

autor

Sniedovich M.

• Department of Mathematics and Statistics, The University of Melbourne, Australia,

Bibliografia

• AHUJA, R.K., MAGNANTI, T.L. and ORLIN, J.B. (1993) Network Flow Theory, Algorithms, and Applications. Prentice-Hall, Englewood-Cliffs, NJ.
• BELLMAN, R. (1952) On the theory of dynamic programming. Proceedings of the National Academy of Sciences, 38, 716-719.
• BELLMAN, R. (1957) Dynamic Programming. Princeton University Press, Princeton. NJ.
• BELLMAN, R. (1958) On a routing problem. Quarterly of Applied Mathematics 16 (1), 87-90.
• BERGE, C. (1958) Theorie des Graphes et ses Applications. Dunod, Paris.
• BERTSEKAS, D. (1991) Linear Network Optimization. The MIT Press, Cambridge, MA.
• BIRD, R. and DE MOOR, O. (1997) The Algebra of Programming. Prentice Hall.
• BRASSARD, G. and BRATLEY, P. (1988) Algorithmics. Prentice-Hall, Englewood Cliffs, NJ.
• GORMEN, T.H., LEISERSON, C.E. and RIVEST, R.L. (1990) Introduction to Algorithms. The MIT Press, Cambride, MA.
• DAELLENBACH, H.G., GEORGE, J.A. and MCNICKLE, B.C. (1983) Introduction to Operations Research Techniques, 2nd Edition. Allyn and Bacon. Boston.
• DANTZIG, G.B. (1960) On the shortest path route through a network. Management Science 6, 187-190.
• DENARDO, E.V. and Fox, B.L. (1979) Shortest-route methods: 1. Reaching, pruning, and buckets. Operations Research 27, 161-186.
• DENARDO, E.V. (2003) Dynamic Programming. Dover, Mineola, NY.
• DIJKSTRA, E.W. (1959) A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269-271.
• DREYFUS, S. (1969) An appraisal of some shortest-path algorithms. Operations Research 17, 395-412.
• EVANS. J.R. and MINIEKA, E. (1992) Optimization Algorithms for Networks and Graphs. Marcel Dekker, NY.
• FORD, L.R. (1956) Network Flow Theory. RAND paper P-923.
• FORD. L.R. and FULKERSON, D.R. (1958) Constructing maximal dynamic flows from static flows. Operations Research 6, 419- 433.
• FORD, L.R. and FULKERSON, D.R. (1962) Flows in Networks. Princeton University Press, Princeton, NJ.
• GALLO, G. and PALLOTTINO, S. (1988) Shortest path algorithms. Annals of Operations Research 13, 3-79.
• GASS. S.I. and HARRIS, C.M. (1996) Encyclopedia of Operations Research and Management Science. Kluwer, Boston, Mass.
• HILLIER, F.S. and LIEBERMAN, G.J. (1990) Introduction to Operations Research, 5th Edition. Holden-Day, Oakland, CA.
• KRUSKAL, J.B., JR. (1956) On the shortest spanning tree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7 (1), 48-50.
• LAWLER, E.L. (1976) Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Whinston, NY.
• LEW, A. (2005) Canonical greedy algorithms and dynamic programming. Journal of Control and Cybernetics, this issue.
• MARKLAND, R.E. and SWEIGART, J.R. (1987) Quantitative Methods: Applications to Managerial Decision Making. John Wiley, New York.
• POLLACK M. and WIEBENSON, W. (1960) Solution of the shortest-route problem - a review. Operations Research 8, 224-230.
• SNIEDOVICH, M. (1992) Dynamic Programming. Marcel Dekker. NY.
• WINSTON, W.L. (2004) Operations Research Applications and Algorithms, Fourth Edition. Brooks/Cole, Belmont, CA.