0
$\begingroup$

I am learning about shortest path algorithm. What is the difference between Dijkstra's method and dynamic programming when finding the shortest root of a path?

$\endgroup$
  • $\begingroup$ Dikjstra is greedy, so what's the difference between greedy algorithms and dynamic programming? $\endgroup$ – Ehsan M. Kermani May 15 '15 at 5:07
2
$\begingroup$

Basically, dynamic programming needs backward induction. For example, if we directly apply dynamic programming to the problem of finding shortest path from A to B, then, the algorithm starts from the destination B and works backward. At the end of the day, the algorithm gives the shortest paths starting from any point and end in B.

However, there are rare cases where we can exploit the symmetry of the problem and prove that the backward induction is equivalent to a forward induction. The shortest path problem is one of these cases.

The basic idea is simple: Suppose we happen to find a route starting from point A to B, which is the shortest, then such route must also be shortest if we start from B and end at A. Thus, every time we want to find a shortest path from A to B, we pretend as if we were looking for a path from B to A and apply dynamic programming to solve the problem from B to A. This "magically" gives us an algorithm which finds out all shortest paths starting from A and end at any point. This is Dijkstra's method.

Thus, it is quite clear that Dijkstra's method is DP. However, it is a special case of DP where we can work things out in a forward way:)

BTW, you might want to check the book written by D. Bertsekas: Dynamic Programming and Optimal Control Vol.1

There is one whole chapter in the book talking about shortest path problem and relations to dynamic programming. Cheers!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.