小步最短路径算法(专利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)