常见的最短路问题分为两类:单源最短路(从一个点到其他所有点)、多源汇最短路(任意两点)
1、在单源最短路问题中若所有的边都是非负数,使用Dijkstra算法;若存在负權边那么可以使用Bellman-Ford算法,SPFA是对前者优化关于算法原理的介绍有很多,这里不再详述
(1)朴素Dijkstra算法,时间复杂度O(n ^ 2)通常在稠密图的时候使用(边的数量级大概为点的数量级的平方),使用邻接矩阵存图可以根据题目要求的时间复杂度来选择使用哪种方法。
示例代码:提供n个点m条边的有向边,存在自环和重边计算一点到另一点的最短距离(题目出自AcWing)
bool st[N]; //记录每一个点是否被用来执行过松弛操作 st[t] = true; //表示t这個点被用来执行过松弛操作了,也表示dist[t]已经确定最小值了
(2)堆优化版的Dijkstra算法,通常稀疏图使用(边与点的数量级大概相当)用邻接表存图,时间复杂度O(mlogn)
这里使用一个小根堆优化朴素方法里面寻找最小的dist的点,使用了贪心的思想
点击“登陆”登陆百度文库后,点击个人中心-已购课程即可找到课程
视频课程不支持缓存或下载。
课程是虚拟产品购买后无法退款或转让,请确认后下单如有问題,请联系百度文库客服
课程是虚拟产品,视频课程不支持缓存或下载
如有问题,请联系百度文库客服
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。