Is Dijkstra's Algorithm a greedy algorithm or a dynamic programming algorithm?

The principle of Dynamic Algorithm is that it tries to calculate the optimal solution by reusing the calculations done for similar subproblems. Greedy Algorithms, on the other hand follows local optimization.It tries to choose the solution which is locally optimum at that particular point of time and may not be the globally optimum solution. The way Djikstra's Algorithm work is similar to the underlying principle of Greedy Algorithms.Hence!

You're completely correct -- Dijkstra's is a DP, and it doesn't make sense to think of the algorithm as greedy. The subproblems here are the computed shortest paths to intermediate vertices. If you were to try and view this as a greedy, choosing a locally optimal solution in the context of a general graph doesn't make much sense. Wikipedia has a brief explanation here: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective edit: From one of the cited papers: "It is crystal clear why DA is commonly regarded as a greedy algorithm: it deploys a greedy rule to determine what city should be processed next." I guess you can view the algorithm as greedy in that light, although that's a little weird.

I would disagree with . Suppose you have a graph  as given below with AB = 1, AC = 2, CD = 4. Suppose we need to compute the shortest distance between A and D. A dynamic programming algorithm solves sub-problems. So intuitively, a sub-problem would be finding the shortest distance to a node that lies in a path between A and D. But Dijkstra's doesn't do that. At A, it simply assumes that the path through B is the shortest because AB < AC. Hence, it is not actually solving a sub-problem, but taking the easiest route possible. So, Dijkstra's is a greedy algorithm and not a DP.

Dijkstra's algorithm is a greedy algorithm because when we get a problem, from the initial point we choose the best possible way just looking at the initial point we choose the best path and follow it and then we do the same with that point. We are not concerned with the distance of other vertex which we might encounter while applying the Dijkstra algorithm. Were as in Dynamic programming algorithm might analyse the complete path first, that is it would take whole graph look at each combination of possible shortest path and then would have given a solution.

Dijkstra’s Algorithm uses the greedy approach to find the solution to a sub-problem(computing the next path at each node). But also, in this algorithm, the previous solutions are stored or “memorized”, so each time after computing the path for a particular vertex, it is just added in the already obtained solution to the previous vertices in order to get the net distance from the origin vertex.    Hence you can say that Dijkstra’s Algorithm uses both, Dynamic Programming Approach as well as Greedy Approach. Like a dynamic programming algorithm, it will examine the previously solved sub-problems (solved using Greedy approach) and then combine their solutions to give the best solution to a given problem.

The way I look at it, what makes Djikstra's algorithm a DP like approach is that they both rely on optimal substructure. AND that we are re-using what we had used in solving a sub-problem, to solve the over all problem. In most dynamic programming problems, the difficult task is to understand how to define a sub-problem. For example, for the standard knapsack "money change" problem, sub-problem is making a change for a smaller amount of money. For a sequence alignment problem, sub-problem is aligning a sub-string. These come naturally as there is a notion of a number which can be split into components, more importantly these are "interval variables", so a natural way to break them is in a series of 1,2,3,4...n. But how do you split a graph into sub-problems? It's very non-intuitive as edges are not ordered. We could order them 1-n, but then what order do we follow them in? Does it have an impact? YES! Djikstra picks this sub-problem in a way which is greedy. So in some sense it has a greediness attached to it. The greedy picking ensures that once a vertex has been covered and all it's outgoing edges relaxed, there is no need to come back to it. Why this works out is not of relevance here, but you can ask for it in the comments if you want me to answer that. In which order do we follow the vertices after the Source vertex, is what is answered greedily. In a nutshell, I see Djikstra as a DP method which relies on greediness to pick the order in which the sub-problems are solved. It's not a counter from i=0 through n, instead, it is computed after every vertex is taken care of. The next vertex is chosen as the one "closest" to the one just completed, and as I mentioned earlier, the reason for why that works out is not relevant here, but let me know if you want to know it! My understanding of these algorithms is fairly limited as I am reading them these days and haven't gotten a chance to imbibe them as such. So, any corrections would be welcome :)

It's greedy in the way it finds the next node to expand, but it uses dynamic programming to compute the optimal distances.

I think Dijktra's algorithm is combination of both - greedy and DP. It uses Greedy approach to make decision about which edge to merge in every iteration. It uses memoization(DP) to actually compute the solution using a solution to a sub-problem. But if I had to really pick one label, I would say Greedy because the decision making approach of the algorithm is Greedy.

It is a dynamic programming algorithm. We are storing the values of distance from source and once a node is visited, we would not be considering it further. This is nothing but storing the distance to a particular node and not changing it. We can hence say that there is no duplication. Dijkstra algorithm can be considered as finding the distance to a destination in a bottom up fashion. Here the only difference is we are finding the distance from source and storing it in the matrix.