Article ID: | iaor20083378 |
Country: | Poland |
Volume: | 35 |
Issue: | 3 |
Start Page Number: | 599 |
End Page Number: | 620 |
Publication Date: | Jan 2006 |
Journal: | Control and Cybernetics |
Authors: | Sniedovich Moshe |
Keywords: | programming: dynamic, education in OR |
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 the author attempts to change this perception by providing a dynamic programming perspective on the algorithm. In particular, the reader is 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.