Dijkstra 算法当中，从 {V}-{S} 集合选择一个 dis 值最小的点 u 加入 {S} 集合。
这个 “选择 u 点”的过程，是一个贪心的过程。
Dijkstra 算法的正确性证明，也是围绕这个贪心是否成立展开的。

松弛操作，是指的遍历 u 点直接相连的，{V}-{S} 当中的点 v，
如果经过 dis[u] + w(u,v) < dis[v] 则更新 dis[v]。

Dijkstra 算法没有动态规划的成分。
另外一个常见的最短路算法 Floyd 是个动态规划算法，这篇博客的作者大概是弄混了。

广度优先算法，应该算是 Dijkstra 在无边权图上的一个特例。
不应该把 Dijkstra 理解为广度优先算法。

另外 Dijkstra 算法并不是固定 O(n^2) 的复杂度。
朴素的，基于枚举所有 {V}-{S} 集合的 Dijkstra 算法确实是 O(n^2) 复杂度。
但是，一般都会对找到 {V}-{S} 集合的 dis 最小点进行堆优化，这时候复杂度是 O(n * logn)。
另外，对于无边权图，可以直接用 queue 代替找 dis 最小点的功能，就是退化到 BFS 了，
这时候算法的复杂度是 O(n)。



【 在 PlutoKey 的大作中提到: 】
: 知乎这篇文章：https://zhuanlan.zhihu.com/p/338414118
: Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法？
: 怎么看出来哪一部分属于贪心？哪部分属于动态规划？
: ...................
--
FROM 220.181.102.*