algorithm - 是Dijkstra算法，动态规划

Question

我见过的所有 Dijkstra 算法的实现都没有递归函数，但我也读到，根据定义，动态规划是一种具有递归函数和“内存”已计算事物的算法。

那么带循环的 Dijkstra 算法是否符合动态规划的条件？
或者为了符合动态算法的条件，我必须将循环更改为递归函数。

Answer 1

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

递归给了我们一个堆栈。但是我们这里不需要堆栈。我们需要一个优先队列。实现 Dijkstra 算法的有效方法是使用 heap (c++ 中的 STL priority_queue)。

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

动态编程不需要以递归方式编写，尽管大多数人更喜欢以递归方式编写。

例如:

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);
}

是DP的递归实现

和

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];
}

是一种迭代的方式来编写它以节省堆栈内存。

记住任何算法

1) 不重新计算已经找到的结果并且

2)利用已有的结果寻找需要的结果

可以称为DP。

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

Dijkstra 是 DP!

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

没有