Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dijkstra's algorithm a greedy or dynamic programming algorithm?

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?

like image 307
vkaul11 Avatar asked Dec 26 '12 08:12

vkaul11


People also ask

What type of algorithm is Dijkstra's algorithm?

Dijkstra's algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph.

Why Dijkstra's algorithm is A greedy algorithm?

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

Is Dijkstra's algorithm static or dynamic?

Another way to solve this problem is to make the Dijkstra algorithm dynamic. The Static Dijkstra algorithm is an iterative algorithm which is used to find the shortest path from a specific vertex of the graph called as source vertex to all the other vertices of the graph (Dijkstra, 1959).

Is dynamic programming A greedy algorithm?

A greedy algorithm chooses the best solution at the moment, in order to ensure a global optimal solution. In dynamic programming, we look at the current problem and the current solution to determine whether to make a particular choice or not.


2 Answers

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

like image 181
Grigor Gevorgyan Avatar answered Oct 19 '22 17:10

Grigor Gevorgyan


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.

like image 32
Zhuoran He Avatar answered Oct 19 '22 19:10

Zhuoran He