迪杰斯特拉(Dijkstra)算法图解
2021/8/5 1:08:10
本文主要是介绍迪杰斯特拉(Dijkstra)算法图解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
基本思想:
- 通过Dijkstra计算图G中的最短路径时,需要指定一个起点D(即从顶点D开始计算)。
- 此外,引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
- 初始时,数组S中只有起点D;数组U中是除起点D之外的顶点,并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻,距离为无穷大。
- 然后,从数组U中找出路径最短的顶点K,并将其加入到数组S中;同时,从数组U中移除顶点K。接着,更新数组U中的各顶点到起点D的距离。
- 重复第4步操作,直到遍历完所有顶点。
起始状态和目标状态:
- S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起点D的距离是3。
- A(22) B(13) C(3) D(0) E(4) F(6) G(12)。
迪杰斯特拉(Dijkstra)算法图解
以上图为例,对迪杰斯特拉进行算法演示(以顶点D为起点)。
原文链接:https://zhuanlan.zhihu.com/p/346558578
这篇关于迪杰斯特拉(Dijkstra)算法图解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)