Dijkstra's algorithm a greedy or dynamic programming algorithm?

algorithm dynamic-programming dijkstra greedy
vkaul11 picture vkaul11 · Dec 26, 2012 · Viewed 12.4k times · Source

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

Grigor Gevorgyan picture Grigor Gevorgyan · Dec 26, 2012

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

Related questions

How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

Read More
What is dynamic programming?

What is dynamic programming? How is it different from recursion, memoization, etc? I have read the wikipedia article on it, but I still don't really understand it.

Read More
Find common substring between two strings

I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails. So if I have 2 strings - string1 = apples string2 = appleses answer = apples Another example, as the string could have more than one word. string1 = apple …

Read More