1159271856 今天给各位分享DIJKSTRA算法的知识，其中也会对dijkstra算法求解最短路径例题进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
关于Dijkstra算法
楼上正解，你找个图自己用此算法实践一下就知道了，从A点出发，发现离A最近的点是B点，那么我们就已经认为A到B的最短距离就是AB了，如果有负数，就指不定冒出个C点,AC+CBAB;或者冒出个DE为很大的负值，AC+CD+DE+EF+FBAB;等等诸如此类的情况。
简单说来，你驾车从家出发到某地沿某条路只需经过一个收费站，但是远在外省某地有个站不但不收你的费，你去了还会给你个千八百万的欢迎光临费，你能说你直接沿着这条路去某地是最省费用的？不计时间成本，绕到外省那个给你钱的地方，再绕回到你的目的地，还能赚钱呢。
而且一般权值为负的图研究也比较少。有些带负权的图，某些点间还没有最小距离呢。中间出个带某条负权很大的边的环圈，绕此一圈所经过的距离反而减少了，那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止。
当然考虑各种自己随便假设出来的变种问题也是很有趣的。比如说边带有多个权值对应多次经过改变的消费，上面的问题有可能变成有解的。话说那个站会后悔，第二次经过它会收回100万，第三次经过收回250万，这样的话你只需要经过一次就够了，问题也是有解的。再比如说对于多权重图，从A点出发经过B点到达C点的最短路线，就不是简单的AB最短路线+BC最短路线了，说不定两者有重合边，第二次经过来个天价就傻眼了。其实这种图貌似应该可以转化成单权重图的，我直觉估计啊，刚随便想出这个问题，还没去思考这个问题的解^_^
dijkstra算法是什么？
迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。
对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。
堆优化
思考
该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。
实现
1、将源点加入堆，并调整堆。
2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3、处理与u相邻的，未被访问过的，满足三角不等式的顶点
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4、若取到的u为终点，结束算法；否则重复步骤2、3。
最短路径算法（Dijkstra）
Dijkstra（ 迪科斯特拉 ）算法是用来解决单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。
下面是一个有权图，求从A到各个节点的最短路径。
第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:
第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标记为已经处理过，如图所示涂色。
第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。
第4步： 重复第3步，2步，直到所有的节点都上色。
最后就算出了从A点到所有点的最短距离。
leetcode 743题
迪杰斯特拉(Dijkstra)算法详解
Dijkstra算法设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0放入S，集合S每并入一个新顶点vi，都要修改源点v0到集合V-S中顶点当前的最短路径长度值。
本例基于邻接矩阵存储的图。
在构造的过程中要设置三个辅助数组：
假设从顶点0出发，即v0=0，集合S最初只包含顶点0，邻接矩阵 edge[][] 表示带权有向图， edge[i][j] 表示有向边i,j的权值，若不存在有向边i,j，则 edge[i][j] 为∞。
Dijkstra算法的步骤如下：
顶点数：5，弧数：10
顶点编号：A B C D E
邻接矩阵：
参考结果：
Dijkstra算法
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。注意该算法要求图中不存在负权边。
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
（1）初始时，S只包含起点D；U包含除D外的其他顶点，且U中顶点的距离为“起点D到该顶点的距离”（例如，U中顶点A的距离为[D,A]的长度，然后D和A不相邻，则A的距离为∞）
（2）从U中选出“距离最短的顶点K”，并将顶点K加入到S中；同时，从U中移除顶点K
（3）更新U中各个顶点到起点D的距离。之所以更新U中顶点的距离，是由于上一步中确定了K是求出最短路径的顶点，从而可以利用K来更新其他顶点到起点D的距离（例如，[D,A]的距离可能大于[D,K]+[K,A]的距离）
（4）重复步骤（2）和（3），直到遍历完所有顶点
发表评论