目录
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算法
算法每次都查找距离起始点最近的点,那么剩下的点距离起始点的距离一定比当前点大。
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算法最清楚的讲解
4,dijkstra算法求最短路径
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算法最清楚的讲解。