Dijkstra's algorithm a greedy or dynamic programming algorithm?

Question

In this post it is described Dijkstras as a greedy algorithm, while here and here it is shown to have connections with dynamic programming algorithms.

Which one is it then?

Answer 1

I would say it's definitely closer to dynamic programming than to a greedy algorithm. To find the shortest distance from A to B, it does not decide which way to go step by step. Instead, it finds all places that one can go from A, and marks the distance to the nearest place. Marking that place, however, does not mean you'll go there. It only means that distance can no longer be made shorter assuming all edges of the graph are positive. The algorithm itself does not have a good sense of direction as to which way will get you to place B faster. The optimal decisions are not made greedily, but are made by exhausting all possible routes that can make a distance shorter. Therefore, it's a dynamic programming algorithm, the only variation being that the stages are not known in advance, but are dynamically determined during the course of the algorithm. You can call it a "dynamic" dynamic programming algorithm, if you like, to tell it apart from other dynamic programming algorithms with predetermined stages of decision making to go through.

Compared with the Kruskal minimal spanning tree algorithm, the difference is clear. In Kruskal's algorithm, you always choose the shortest edge that does not lead to a cycle, and then the next shortest edge, and so on. The optimal strategies are chosen step by step and only one choice gets played out in the algorithm. The other possibilities are not checked or compared algorithmically, even though mathematically a theorem guarantees that they will not be optimal. So to me Kruskal is greedy but Dijkstra is dynamic programming.

Answer 2

It's greedy because you always mark the closest vertex. It's dynamic because distances are updated using previously calculated values.