贪心算法dijkstra

❶ 迪杰斯特拉算法的本质是贪心还是动态规划

贪心是一种特殊的动态规划，动态规划的本质是独立的子问题，而贪心则是每次可以找到最优的独立子问题。
贪心和动归不是互斥的，而是包含的，贪心更快，但约束更强，适应范围更小。
动归和bfs的关系也是一样的。
展开一点讲，在求解最优化问题时，有多个解。而求解的过程类似一个树，我们称之为求解树。
一般的求解树真的是一棵树，所以我们只能用bfs来搜索，顶多剪枝。
有些特殊的求解树，中间很多结点是重合的，结点个数比所有搜索分支的个数少很多个数量级。这类问题较特殊，我们可以保存中间的搜索过程。而记忆化搜索和动态规划本质上就是一个东西，快就快在可以不用重复计算很多中间结果（所谓的最优子问题）。
还有一些特殊的求解树，更特殊，它们不止有很多重复结点，而且每次选择分支的时候，我们可以证明只要选择一个分支，这个分支的解就一定比其他选择更优。这类问题就是贪心了，
所以bfs，dp，贪心三个方法都是解决最优化问题的方法，根据问题的不同，约束越大的问题可以用越快的方法，越慢的方法可以解决的问题越普适。
动态规划的状态转移函数，可以抽象成这样一种函数：
f(x)=g(f(x1), f(x2), f(x3), ... f(xn))
其中f就是我们说的独立问题，每个f都有一个唯一值，也就是没有后效性。
贪心也是这个函数，但可以证明：
f(xi) >= f(x1|x2|...|xn)
那么我们就不用再去计算除了f(xi)以外的任何子状态了，所以就更快
而标准的bfs，虽然也有
f(x)=g(f(x1), f(x2), f(x3), ... f(xn))
但是因为对于任意的f(x)，它的子问题f(xi)的输入状态xi都不同（换一种思路也可以说f(xi)在不同的路径下值都不同，本质上是我们怎么定义xi，到底是狭义的参数还是广义的状态），所以无法使用内存去换取时间，就只能去遍历所有状态了。

❷ dijx是什么意思

Dijkstra算法是荷兰计算机科学家Edsger W. Dijkstra于1956年提出的，是一种解决单源最短路径问题的贪心算法。它通过优先队列来存储和访问每个顶点的距离，从而快速找到最短路径。该算法广泛应用于地图应用、交通路线计算、图形文件路径查找和网络路由算法等领域。在实际应用中，Dijkstra算法可以通过堆优化或队列优化实现，以降低时间复杂度并提高算法效率。

❸ Dijkstra算法

迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家狄克斯特拉在1959年提出的。它是一种求解有权图中最短路径的算法，主要特点是采用贪心算法的策略，从起始点开始，每次遍历到距离始点最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

迪杰斯特拉算法求的是单源最短路问题。其实现过程如下：

示例中我们可以发现，这里的迪杰斯特拉算法只适用于边权均为正的图。Dijkstra模板题如下：

给定一个有n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。输入格式：第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。输出格式：输出一个整数，表示1号点到n号点的最短距离。如果路径不存在，则输出-1。数据范围：[公式]，[公式]，图中涉及边长均不超过10000。输入样例：3 3 1 2 2 2 3 1 1 3 4 输出样例：3

分析：由本题的点和边的数据范围可知，这是一个稠密图，因此使用邻接矩阵来存储图。（朴素Dijkstra正是用来处理稠密图的）注意：本题有重边和自环。由于边权为正，所以自环一定不会在最短路中。而对于重边，我们存下最短边即可。

代码实现：时间复杂度为[公式]。对于稀疏图（m与n数据范围接近时），Dijkstra还有另外一种形式：堆优化Dijkstra。优化主要在寻找距离最小的点的操作上。堆有两种实现方式，之前已经有写过手写堆，这里使用另外一种堆的实现方式：优先队列。由于是稀疏图，存储方式需要改成邻接表形式。其思路和朴素Dijkstra一致。

代码实现：时间复杂度为[公式]。

以上就是朴素Dijkstra算法和堆优化Dijkstra算法。都是用于单源正权边最短路。未必优化版的就是更好的，朴素版适合稠密度，堆优化版适合稀疏图。