Dijkstra的算法是一种贪婪或动态的编程算法？

Question

在这篇文章中,它将Dijkstras描述为一种贪婪的算法,而在这里和这里它被证明与动态编程算法有联系.

那是哪一个呢？

Answer 1

这很贪婪,因为你总是标记最近的顶点.它是动态的,因为距离是使用先前计算的值更新的.

Answer 2

我会说它绝对更接近动态编程而不是贪婪算法.要找到从A到B的最短距离,它不会一步一步地决定走哪条路.相反,它会找到一个可以从A出发的地方,并标记到最近的地方的距离.然而,标记那个地方并不意味着你会去那里.这只意味着假设图的所有边都是正的,距离不能再缩短.算法本身没有很好的方向感,因为哪种方式可以让你更快地放置B. 最佳决策不是贪婪的,而是通过耗尽可能缩短距离的所有可能路线来做出的.因此,它是一种动态编程算法,唯一的变化是这些阶段不是事先知道的,而是在算法过程中动态确定的.如果您愿意,可以将其称为"动态"动态编程算法,将其与其他动态编程算法区分开来,并确定预定的决策阶段.

与Kruskal最小生成树算法相比,差异很明显.在Kruskal算法中,您始终选择不会导致循环的最短边,然后选择下一个最短边,依此类推.逐步选择最优策略,在算法中只有一个选择.其他可能性不是通过算法检查或比较的,即使数学上定理保证它们不是最优的.所以对我来说Kruskal很贪婪,但Dijkstra是动态编程.