基于贪心思想,只适用于边长为非负数的图
O(mlogn)
算法流程:
1、 初始化的dist[1]=0,其余节点的dist为正无穷
2、 找出一个未被标记、dist[x]最小的节点x并标记
3、 扫描x的所有出边(x,y,z),若dist[y]>dist[x]+z,则更新dist[y]
4、 重复2、3,直到所有节点被标记
原创 | 2023-01-01 13:56:28 |浏览:1.6万
基于贪心思想,只适用于边长为非负数的图
O(mlogn)
算法流程:
1、 初始化的dist[1]=0,其余节点的dist为正无穷
2、 找出一个未被标记、dist[x]最小的节点x并标记
3、 扫描x的所有出边(x,y,z),若dist[y]>dist[x]+z,则更新dist[y]
4、 重复2、3,直到所有节点被标记
Copyright 2005-2020 www.kxting.com 版权所有 | 湘ICP备2023022655号
声明: 本站所有内容均只可用于学习参考,信息与图片素材来源于互联网,如内容侵权与违规,请与本站联系,将在三个工作日内处理,联系邮箱:47085,1089@qq.com