Dijkstra's Algorithm| Info-Gap Decision Theory | Voodoo Decision-Making | Robust Decisions | Severe Uncertainty | Satisficing vs Optimizing | Maximin |
Dijkstra's AlgorithmThis without any doubt is one of the most famous and useful algorithms in OR/MS and CS.
Moshe's new book! Yet ....!
It is baffling how this algorithm is presented and explained in the official literature and lecture notes.
For many years this item had been on my "to do" list.I finally decided to do something about it.
The result: an education-oriented paper addressing a number of key issues regarding the origin of the algorithm and its relationship to other well known algorithms. It includes a number of online interactive modules for experimentation with the algorithm.
Dijkstra's Algorithm: The DP Connection I strongly recommend this paper to anyone teaching this subject.
In 2010 I decided to edit the WIKIPEDIA entry on this algorithm to inform the public on the DP connection. I added the following subsection
Dynamic programming perspective
From a dynamic programming point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.[4][5][6]
In fact, Dijkstra's explanation of the logic behind the algorithm,[7] namelyProblem 2. Find the path of minimum total length between two given nodes P and Q.is a paraphrasing of Bellman's famous Principle of Optimality in the context of the shortest path problem.
We use the fact that, if R is a node on the minimal path from P to Q, knowledge of the latter implies the knowledge of the minimal path from P to R.This subsection is still there (December 26, 2021).
Incidentally, about a year or so ago I was contacted by email by one of Dijkstra's former colleages, who tried to explain to me why Dijkstra did not discuss the connection to DP in his famous 1959 article. This colleage claimed that in 1959 Dijkstra did not know anything about DP and the Principle of Optimality.
I should stress that my criticisim is not directed at Dijkstra himself, but at the younger generation of computer scientists who seem to be unaware of the intimate relationship between this famous algorithm and DP.
In any case, I encourage you to visit the tutOR project for more details on the relationship between DP and Dijkstra's Algorithm.
Disclaimer: This site, its contents and style, are the responsibility of its owner and do not represent the views, policies or opinions of the organizations he is affiliated with.
