Is Dijkstra's algorithm, dynamic programming

Question

All implementation of Dijkstra's algorithms I have seen do not have a recursive function, but I have also read that by definition dynamic programming is an algorithm with a recursive function and "memory" of things already calculated.

So is Dijkstra's algorithm with a loop qualified as dynamic programming?
Or in order to qualify as dynamic algorithm I have to change a loop into a recursive function.

You can have dynamic programming with recursive or iterative solutions. It's the approach of simplifying the problem into subproblems that is dynamic, not whether or not you solve it recursively or iteratively. — wkl, Jun 10 '14 at 12:16

cegprakash · Answer 1 · 2019-02-01T14:21:21.253

All implementation of Dijkstra's algorithms I have seen do not have a recursive function

Recursion gives us a stack. But we don't need a stack here. We need a priority queue. The efficient way to implement Dijkstra's algorithm uses a heap (stl priority_queue in c++).

but I have also read that by definition dynamic programming is an algorithm with a recursive function and "memory" of things already calculated.

Dynamic Programming need not be written in a recursive way though most people prefer to write it in a recursive way.

For example:

int dp[MAX]={-1,-1,...};
find fibonacci(int nthTerm){
   if(n <= 1) return n;
   if(dp[n]!=-1) return dp[n];
   return dp[n]=fibonacci(n-1)+fibonacci(n-2);
}

is a recursive implementation of DP

and

int dp[MAX]={0,1,-1,-1,-1,..};
int lastFound = 1;
int fibonacci(int nthTerm){
    for(int i=lastFound+1;i<=n;i++){
       dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

is an iterative way of writing it to save stack memory.

Remember that any algorithm

1) that does not recalculate the result that is already found and

2) uses the existing result to find the required result

can be called as a DP.

So is Dijkstra's algorithm with a loop qualified as dynamic programming?

Dijkstra is DP!

Or in order to qualify as dynamic algorithm I have to change a loop into a recursive function.

No

As iterative functions save stack memory (as described in above ans) , some modern languages like kotlin automatically convert recursive functions into non recursive ones. https://softwareengineering.stackexchange.com/questions/202983/can-and-do-compilers-convert-recursive-logic-to-equivalent-non-recursive-logic Infact every recursive can be converted into non recursive functions and vice versa. https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration — Apoorva Jain, Jan 23 '19 at 13:22

score 3 · Answer 2 · answered Feb 15 '15 at 04:53

There is a paper about it entitled "Dijkstra’s algorithm revisited: the dynamic programming connexion" by Moshe Sniedovich. http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf

The paper claim that Dijkstra’s algorithm is strongly inspired by Bellman’s Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence.

score 2 · Answer 3 · answered Jan 25 '18 at 14:43

Dijkstra's Algorithm is like a water filling algorithm. At each step it chooses local minima that's the reason why many consider it as Greedy Algorithm. If you will try this same algorithm with choosing any arbitrary path not the local minima, then you will come to know that it's still working. Choosing a local minima is just because of filling water optimally as I mentioned earlier that it's like water filling algorithm. So, the main concept behind Dijkstra's Algorithm is to store the previous result to predict the upcoming result and that is what Dynamic Approach is.

For more details refer below link

Why does Dijkstra's algorithm work?

you have to explain what is water filling problem :P – cegprakash Feb 01 '19 at 13:45 — cegprakash, Feb 01 '19 at 13:45

score -2 · Accepted Answer · answered Jun 10 '14 at 12:21

-2

You address two questions:

Dynamic Algorithms mean breaking a procedure down into simpler tasks. Several dynamic algorithms iclude the idea of recursion but are not limited too..

Considering Dijkstra's algorithm the clasic solution is given by a for loop and is not a dynamic algorithm solution.

However, From a dynamic programming point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

In fact, Dijkstra's explanation of the logic behind the algorithm, namely:

Problem 2. Find the path of minimum total length between two given nodes P and Q.

Note: taken from Wikipedia

answered Jun 10 '14 at 12:21

apomene

14,282
9
46
72

Also from [wikipedia](http://en.wikipedia.org/wiki/Dynamic_programming): Sometimes, applying memoization to a naive basic recursive solution already results in an optimal dynamic programming solution; however, many problems require more sophisticated dynamic programming algorithms. Some of these may be recursive as well but parametrized differently from the naive solution. Others can be more complicated and cannot be implemented as a recursive function with memoization. Examples of these are the two solutions to the Egg Dropping puzzle below. – Kicsi Jun 10 '14 at 12:22
5

Dijkstra's is not an approximation. – pjs Jun 10 '14 at 15:36

Is Dijkstra's algorithm, dynamic programming

4 Answers4

Linked