目录
1,dijkstra算法是什么?
Dijkstra算法是由荷兰计算机科学家狄克斯特拉(Dijkstra)于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。 其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。 不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。 举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。 Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E所有边的集合,而边的权重则由权重函数w: E→[0,∞]定义。 因此,w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。 已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中,找到从一个顶点s到任何其他顶点的最短路径。
2,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。
3,最短路径 | 深入浅出Dijkstra算法(一)
上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ,它可以方便的求得 任意两点的最短路径, 这称为 “多源最短路”。 这次来介绍 指定一个点(源点)到其余各个顶点的最短路径, 也叫做 “单源最短路径”。 例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。 与 Floyd-Warshall 算法一样,这里仍然 使用二维数组 e 来存储顶点之间边的关系, 初始值如下。 我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程, 我们可以称 dis 数组为 “距离表”, 如下。 我们将此时 dis 数组中的值称为 最短路的“估计值”。 既然是 求 1 号顶点到其余各个顶点的最短路程, 那就 先找一个离 1 号顶点最近的顶点。 通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。 当选择了 2 号顶点后,dis[2]的值就已经从“估计值”变为了“确定值”, 即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。 为什么呢?你想啊, 目前离 1 号顶点最近的是 2 号顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 1 号顶点到 2 号顶点的路程进一步缩短了。 因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短,对吧 O(∩_∩)O~ 既然选了 2 号顶点,接下来再来看 2 号顶点 有哪些 出边 呢。有 2->3 和 2->4 这两条边。 先讨论 通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。 也就是说现在来比较 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程,dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程,e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点,再通过 2->3 这条边,到达 3 号顶点的路程。 我们发现 dis[3]=12,dis[2]+e[2][3]=1+9=10,dis[3]>dis[2]+e[2][3],因此 dis[3]要更新为 10。这个过程有个专业术语叫做 “松弛” 。即 1 号顶点到 3 号顶点的路程即 dis[3],通过 2->3 这条边 松弛成功。 这便是 Dijkstra 算法的主要思想: 通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。 同理通过 2->4(e[2][4]),可以将 dis[4]的值从 ∞ 松弛为 4(dis[4]初始为 ∞,dis[2]+e[2][4]=1+3=4,dis[4]>dis[2]+e[2][4],因此 dis[4]要更新为 4)。 刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为: 接下来,继续在剩下的 3、4、5 和 6 号顶点中,选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组,当前离 1 号顶点最近是 4 号顶点。此时,dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边(4->3,4->5 和 4->6)用刚才的方法进行松弛。松弛完毕之后 dis 数组为: 继续在剩下的 3、5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 3 号顶点。此时,dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边(3->5)进行松弛。松弛完毕之后 dis 数组为: 继续在剩下的 5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 5 号顶点。此时,dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边(5->4)进行松弛。松弛完毕之后 dis 数组为: 最后对 6 号顶点的所有出边进行松弛。因为这个例子中 6 号顶点没有出边,因此不用处理。 到此,dis 数组中所有的值都已经从“估计值”变为了“确定值”。 最终 dis 数组如下,这便是 1 号顶点到其余各个顶点的最短路径。 OK,现在来总结一下刚才的算法。 Dijkstra算法的基本思想是:每次找到离源点(上面例子的源点就是 1 号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。 基本步骤如下: 在 博客 中看到两个比较有趣的问题,也是在学习Dijkstra时,可能会有疑问的问题。 当我们看到上面这个图的时候,凭借多年对平面几何的学习,会发现在“三角形ABC”中,满足不了 构成三角形的条件(任意两边之和大于第三边)。 纳尼,那为什么图中能那样子画? 还是“三角形ABC”,以A为起点,B为终点,如果按照平面几何的知识, “两点之间线段最短”, 那么,A到B的最短距离就应该是6(线段AB),但是,实际上A到B的最短距离却是3+2=5。这又怎么解释? 其实,之所以会有上面的疑问,是因为 对边的权值和边的长度这两个概念的混淆, 。之所以这样画,也只是为了方便理解(每个人写草稿的方式不同,你完全可以用别的方式表示,只要便于你理解即可)。 PS:数组实现邻接表可能较难理解,可以看一下 这里 参考资料: Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点,更新与其相邻的点的路程。当所有边权都为正时,由于不会存在一个路程更短的没扩展过的点,所以这个点的路程永远不会再被改变,因而保证了算法的正确性。 根据这个原理, 用Dijkstra算法求最短路径的图不能有负权边, 因为扩展到负权边的时候会产生更短的路径,有可能破坏了已经更新的点路径不会发生改变的性质。 那么,有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法(即“单源最短路径”问题)呢?答案是有的, Bellman-Ford算法 就是一种。(我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题,也要求图的边权均为正) 通过 邻接矩阵 的Dijkstra时间复杂度是 。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N),这里我们可以用 优先队列(堆) 来优化,使得这一部分的时间复杂度降低到 。这个我们将在后面讨论。
4,最短路径 - Dijkstra算法
算法每次都查找距离起始点最近的点,那么剩下的点距离起始点的距离一定比当前点大。
1.选定A节点并初始化,如上述步骤3所示
2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合
3.这时候 A->B, A->C 都为3,没关系。其实这时候他俩都是最短距离,如果从算法逻辑来讲的话,会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' B距离 其实为 A->D->B
思路就是这样,往后就是大同小异了
算法结束
(图片来源于网络)
Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。在上图中,粉红色的结点是初始结点,蓝色的是目标点,而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier)。因而Dijkstra算法可以找到一条最短的路径,但是效率上并不高。
数据结构--Dijkstra算法最清楚的讲解