迪杰斯特拉算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了迪杰斯特拉算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1225字,纯文字阅读大概需要2分钟。
内容图文
![迪杰斯特拉算法](/upload/InfoBanner/zyjiaocheng/736/c86b890fbc84474a953442b280b91e3c.jpg)
迪杰斯特拉算法(SPF:Shortest Path First最短路径算法)
1. 算法思想
输入(即已知条件): 有权重的无向图G={E,V},V是顶点的集合,E是边的集合 ,每一边皆有权重(大于零),源节点s和目的节点d都属于集合V(s∈V, d∈V)。
输出(即求得的结果): 源节点s到所有其它节点的最短路径的长度。
2. 初始化阶段,除了起点A外,所有节点的距离dist设置为无穷大。
3. 更新邻居的距离
起点A的邻居为为B,D,根据边AB、AD的权重,将其距离分别更新为
Distance(B)=2,Distance(D)=1
4. 移除有最小距离的点D
由于A的邻居节点是B和D,Distance(B)=2>Distance(D)=1,所以移除D点。
5. 以移除的D为起点进行更新
分别计算D的邻居节点的距离,等于AD的权重,加上DC、DFDG、DE、DB的权重。
6. 移除B
在未移除的节点中,选择距离最小的B( distance =2)移除,并且更新邻居
注意:distance(D) D不用更新,因为D已知; distance(E)也不用更新,因为BD+DE=5,比前面计算的值3要大。
7. 移除E
在未移除的节点中,选择距离最小的E(distance =3)移除,并且更新邻居
由于邻居B、D已经移除,所以不用更新; distance(G)也不用更新,因为BE+GE=16>distance(G)=5,比前面计算的值5要大。
8. 移除C
在未移除的节点中,选择距离最小的C(distance =3)移除,并且更新邻居
9. 移除G
10. 最后移除F,并按前面原则更新各节点距离
到此,可以得到起点A到各个顶点的最短距离,完成了dijkstra的算法过程。
内容总结
以上是互联网集市为您收集整理的迪杰斯特拉算法全部内容,希望文章能够帮你解决迪杰斯特拉算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。