最短路径 - 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 距离' < 'A 到 C,E 的距离' ) ,如图所示这时候A->B距离 其实为 A->D->B
思路就是这样,往后就是大同小异了
算法结束
(图片来源于网络)
Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。在上图中,粉红色带虚答的结点是初始结点,蓝色的是目标点,而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier)。因而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 距离' < 'A 到 C,E 的距离' ) ,如图所示这时候A->B距离 其实为 A->D->B
思路就是这样,往后就是大同小异了
算法结束
(图片来源于网络)
Dijkstra算法保证能找到一条从初始点到目标点的最短路径,只要所有的边都有一个非负的代价值。在上图中,粉红色带虚答的结点是初始结点,蓝色的是目标点,而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的,因而形成探测过程(exploration)的边境(frontier)。因而Dijkstra算法可以找到一条最短的路径,但是效率上并不高。
数据结构--Dijkstra算法最清楚的讲解
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询