Dijkstra's algorithm revisited: the dynamic programming connexion

Dijkstra's algorithm revisited: the dynamic programming connexion

0.00 Avg rating0 Votes
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:
Keywords: programming: dynamic, education in OR
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 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.

Reviews

Required fields are marked *. Your email address will not be published.