algorithm - Dijkstra 算法是贪心算法还是动态规划算法？

Question

在这篇文章中，将 Dijkstras 描述为一种贪心算法，而这里和这里显示它与动态规划算法有联系。

那是哪一个呢？

Answer 1

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

Answer 2

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

与 Kruskal 最小生成树算法相比，区别很明显。在 Kruskal 算法中，您总是选择不会导致循环的最短边，然后选择下一个最短边，以此类推。最优策略是逐步选择的，算法中只选择一个选项。其他可能性不会在算法上进行检查或比较，即使在数学上一个定理保证它们不会是最优的。所以对我来说，Kruskal 是贪婪的，但 Dijkstra 是动态规划。