Difference between Dynamic programming and Dijkstra's Algorithm

Question

Can any one please clarify does Dijkstra's Algorithm come under Dynamic Programming or not. Why do we call that Floyd warshall algorithm comes under Dynamic programming approach. I am not able to trace out the difference between them. When i tried doing this i actually encountered a doubt that what exactly Dynamic programming means? And also Dijkstra's is quoted as Greedy approach does that mean it is not always correct? Moreover does the result for this two algorithms differ? Can any one explain in detail please.

score 3 · Answer 1 · answered Dec 07 '12 at 06:57

3

Dynamic programming is where you inductively use sub-problems to solve the problem.

On the other hand, greedy algorithms try to solve a global optimization problem by making locally optimal steps. Sometimes these local steps take you to the global optimum (as in the case of Dijkstra's algorithm) and sometimes it may not (like in the change making problem).

answered Dec 07 '12 at 06:57

tskuzzy

35,812
14
73
140

Finally does the result obtained is same for both the approaches? – user1275375 Dec 07 '12 at 06:59
1

@user1275375 DP and Greedy techniques are used to solve problems to find `an` optimal solution and not `the` optimal solution. So in this case, you might have n number of shortest paths of the same length. Either greedy or DP would give you one of those shortest paths - so the results might differ if you see the actual nodes traversed. However, the resulting path would always be the shortest one among all present. – nightlytrails Dec 07 '12 at 07:10
My question is if i consider these two algorithms for finding Shortest path between two cities than i think they sholud be giving the same output because they give the best optimal solution. Please correct me if iam wrong – user1275375 Dec 07 '12 at 07:23
@user1275375 yes, they all would give `the` best optimal solution in terms of `distance` between the two cities. The distance would be the same. However, the path traversed might be different. – nightlytrails Dec 07 '12 at 07:25

score 0 · Answer 2 · answered Dec 07 '12 at 06:53

0

Dynamic programming (DP) and Greedy approach is a methodology - a concept - just like Recursion; they are not any particular algorithm.

Dijaktra's algorithm - to quote from wikipedia -

is a graph search algorithm that solves the single-source shortest path problem for a graph > with nonnegative edge path costs, producing a shortest path tree

Dijaktra's algorithm might use DP technique to solve the shortest path problem.

answered Dec 07 '12 at 06:53

nightlytrails

2,448
3
22
33

I would not classify Dijkstra as a dynamic programming algorithm. It is greedy more than anything else. – tskuzzy Dec 07 '12 at 06:54
I have edited my answer to say Dijkstra `might` use DP. – nightlytrails Dec 07 '12 at 06:55

score 0 · Answer 3 · edited May 23 '17 at 10:34

Dynamic programming is programming methodology by which we can solve complex problem by breaking them down into simpler sub-problems.by storing previously computed subproblem values in an memory instead of recomputing.this can be understood by this example ..

 public static int fib(int n) {
 if (n < 2) {
 return n;
 }
 int[] f = new int[n];
 f[0] = 0;
 f[1] = 1;
 for (int i=2; i<n; i++) { // store the Fibonacci numbers
 f[i] = f[i-1] + f[i-2];
 }
  return f[n-1] + f[n-2];
}

While Dijkstra is graph search algorithm.

and for difference between Dynamic programming,Greedy approach you can see this post

Divide and conquer, dynamic programming and greedy algorithms! greedy-algorithms

Difference between Dynamic programming and Dijkstra's Algorithm

3 Answers3