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.

Answer 1

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

Answer 2

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.