关于信息学竞赛中最短路算法的研究
2021-08-27范俊怡刘栩含
科技与创新 2021年16期
范俊怡,刘栩含,龙 玲
(四川省南充高级中学,四川 南充637000)
1 引言
信息学竞赛考察内容广泛,包含贪心算法、分治算法、动态规划以及图论相关算法等。其中图论在计算机中扮演着重要的角色,许多问题都需要抽象成图,然后运用图论的相关算法来解决。最短路问题是图论中一个经典问题,曾多次出现在信息学竞赛考场上;同时最短路也与实际生活息息相关,比如常用的地图导航涉及的路径规划使用的核心算法就是最短路算法,因此竞赛生需要牢牢掌握最短路的相关算法。
2 最短路问题
最短路问题主要是研究在带权连通图中,一个结点到达另一个结点的所有路径中找权值和最小的一条路径。所谓带权连通图指图中任意一条边是带有权值的,并且任意两结点之间至少存在一条路径。
在信息学竞赛中,主要给学生讲解四种常用的求解最短路问题的算法,这四种算法各有优劣,对于不同的竞赛题目,推荐学生选择较优的算法解题。
3 最短路算法
3.1 Floyed-Warshall算法
Floyed-Warshall算法又称弗洛伊德最短路算法,该算法是利用动态规划算法的思想求解最短路问题的算法,复杂度为O(n3)。调用一次Floyed-Warshall算法就可以直接求出一个n阶图的任意两个结点之间的最短路,称之为多源最短路算法。
优点:学生容易理解和记忆,代码实现简单;可以处理存在负边权的图;有向图和无向图都可适用。
缺点:时间复杂度高,不适合大数据求解;必须用邻接矩阵存储数据,内存占用大,适用于稠密图。……
登录APP查看全文
