找回密码
 注册帐号

扫一扫,访问微社区

达维安爵士

迪杰斯特拉算法思路

49 2019-1-21 12:14 |个人分类:算法| 算法, 迪杰斯特拉

首先来了解下迪杰斯特拉算法是什么,它有什么作用。

给出这样一个问题:求出下图中A点到E点所花费最少的路线


这就是一种带权的图,求两节点花费值最少,迪杰斯特拉算法就到了用武之地。
当然,我们普通人一眼就能看出来,最短距离肯定是A-C-D-E。3+40+25=68元
但是电脑自身是看不出来的(当然你也可以写个人工智能去“看”23333)
下面就是正式运行迪杰斯特拉算法的步骤总结:
1:找出当前已知最便宜的节点。
2:更新该节点的邻居花费。
3:重复以上,直到对所有节点都如此执行过。
4:计算最终答案路径。

接下来按照这个方式进行对问题的解答实操。

从起点A开始,计算机进行一个选择,A-B的花费为10,A-C的花费为3,至于前往其他节点的距离,暂时设为无穷大,不能直接到达。
然后创建一个散列表来记录一下:

通过简单的比较,我们知道起点到C点的距离更近,然后以C点为下一个计算点,计算C到它的邻居点的最近距离(排除已计算过的起点A)

C-B=3+20=23>B,不更新

C-D=3+40=43<无穷大,更新

C-E=3+500<无穷大,更新

由于23>10,即直接到B点还是比通过C点到B点还是要便宜些,就不更新B点的值

然后把C点排除,重复以上步骤,找到了除了C点以外最近距离是B点

接下来计算B点到各个邻居的路线花费

B-C=10+20=30>3,不更新

B-D=10+50=60>43,不更新

再次重复,计算除B,C点以外的点,发现最短的是D,43<503

然后是D点到各邻居点的花费

D-B=43+50=93>10,不更新;

D-C=43+40=83>3,不更新;

D-E=43+25=68<503,更新!

再次重复,排除BCD,剩下最后一个E,其实就已经完了,到达终点E则不用再执行,然后开始从E点,依次往上找到其最近父节点,就是最终的答案路线了

答案路线即为: E-D-C-A =>A-C-D-E





评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册帐号