小步最短路径算法（专利GAI22CN4344）
【摘要】 小步最短路径算法，
避免Dijstras需要多次更新节点到起点的最短路径的值，
可一次性确定节点的最短路径的数值。
Dijstras需要多次更新节点到起点的最短路径的值；
GAI22CN4344可一次性确定节点的最短路径的数值。
设D为迭代起点。Dijstras路径查找过程为：
- 同时更新节点C和E的路径值；
- 确定C确定了最短路径；
- 更新节点B、F的路径值，E路径值不需要更新；
- 确定E的最短路径；
- 更新F和G的路径值；
- ....
Dijstras算法这种简单的更新节点路径值的策略，存在一个缺陷，即无法通过硬件的并发提高算法的效率。
GAI22CN4344每次只更新确定最短路径的节点的路径值。 Dijstras路径查找过程为：
- 路径值初始化为0（不需要更新节点E和C的路径值）；
- 路径值增加最小的量，以使得确定最短路径的节点数量不为0，且该数量最小：
- 路径值更新为3-->确定节点C的最短路径（不需要更新节点B、F和E的路径值）；
- 路径值更新为4-->确定节点E的最短路径（不需要更新节点F和G的路径值）；
- 路径值更新为6-->确定节点F的最短路径（不需要更新节点A、B和G的路径值）；
- ...
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）