All implementations of Dijkstra's algorithms that 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. An efficient way to implement Dijkstra's algorithm uses heap (stl priority_queue in c ++).
but I also read that, by definition, dynamic programming is an algorithm with a recursive function and the “memory” of things already calculated.
Dynamic programming should not be written in a recursive way, although most people prefer to write it in a recursive way.
For instance:
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); }
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]; }
This is an iterative way of writing to save stack memory.
Remember that any algorithm 1) that does not recount a result that is already found, and 2) uses an existing result to find the desired result, can be called DP.
So is Dijkstra's algorithm with a loop qualified as dynamic programming?
Dijkstra is a DP!
Or in order to qualify as a dynamic algorithm, I need to convert the loop into a recursive function.
no