Journal article

Dijkstra's algorithm revisited: the dynamic programming connexion

Moshe Sniedovich

CONTROL AND CYBERNETICS | POLISH ACAD SCIENCES SYSTEMS RESEARCH INST | Published : 2006

Abstract

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 d..

View full abstract

University of Melbourne Researchers