关于dijsktra和prim的算法特殊解释
2021/7/8 17:06:27
本文主要是介绍关于dijsktra和prim的算法特殊解释,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言:
本文为:https://www.cnblogs.com/lihanyu116/p/14982524.html 补充。
对于这种情况,我们按照dijsktra和prim的算法的思想,选择点1为起点后。寻找点1的最短边,那么这时我们会选到1--2这条边权为1的边,那么记录下点2为nixt,然后再从点nixt更新并寻找寻找。
那么显然选择点2是错误的。
但是我们的这种dijsktra和prim的算法是正确的,为什么呢?
我们一步步来模拟一下他运算的过程。
首先我们选择点1后,更新此时的cost[2]=1,cost[3]=2。
我们将二者比较,明显到点2短,记录nixt=2;
然后更新点nixt(2)到点3的值。
重点来了,此时cost[3]仍然等于2,所以此时
cost[j]>map [nixt][j] 即 cost[3]>map [2][3]
这个条件显然是不成立的,所以不去更新。cost[3]还是我们第一次更新的值。
此时从1到3的最短路,为2。
上面那句话可以通俗的理解为:
已经存储的“伪最短路”(cost[j])和我们寻找的“最新的最短路”(map[nixt][j])比较选择短的一个。
其实对于哪怕像多层图最短路,也是运用的这种思想。
如有不足,请指出,谢谢!
这篇关于关于dijsktra和prim的算法特殊解释的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06vue 新建功能多条数据(还没和后端交互)还能看详情 数据是前端缓存到本地吗?-icode9专业技术文章分享
- 2024-05-30React Native常用组件-点击组件
- 2024-05-30uniapp+vue3+uv-ui手机端后台OA管理模板
- 2024-05-29Python网络爬虫的时候json=就是让你少写个json.dumps()
- 2024-05-27React Native常用组件-展示组件
- 2024-05-27React Native常用组件-列表组件
- 2024-05-09vue3开发前端表单缓存自定义指令,移动端h5必备插件
- 2024-05-09React Hooks在class组件中的使用方式
- 2024-03-30[OIDC in Action] 2. 基于OIDC(OpenID Connect)的SSO(纯JS客户端)
- 2024-03-29terraform jsonencode