老师，Dijkstra 是动态规划还是贪心？

Question

老师，请解释下Dijkstra 是动态规划，还是贪心？ 为什么？
能详细说明下动态规划与贪心的区别么

Answer 1

liuyubobobo 2018-10-23 01:08:08

在算法思路上，可以说即包含了动态规划的思想，又包含了贪心的思想。

依然是，以我在《算法与数据结构》中的代码为例：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/09-Shortest-Path/Course%20Code%20(C%2B%2B)/03-Implementation-of-Dijkstra/Dijkstra.h

动态规划的地方在于，使用distTo数组，存储了从s到每一个节点的最短路径（状态存储），同时，在逻辑过程中，应用相应的转移方程进行状态修改（我上一个问题回答你的两行代码）：）

贪心的地方在于，每一次找到当前未处理的那个距离s最近的节点，继续后续的处理。

注意：无论是动态规划，还是贪心，都只是算法思想而已。一个算法，可以融合多个算法思想。比如快速排序，首先，他是分治算法（将整个待处理区间一份为二），其次，他也是个随机算法（随机调选pivot是的递归深度的期望达到logn）：）

加油！：）

• 提问者 triump #1

  非常感谢！