关于信息学竞赛中最短路算法的研究

范俊怡，刘栩含，龙 玲

（四川省南充高级中学，四川 南充637000）

1 引言

信息学竞赛考察内容广泛，包含贪心算法、分治算法、动态规划以及图论相关算法等。其中图论在计算机中扮演着重要的角色，许多问题都需要抽象成图，然后运用图论的相关算法来解决。最短路问题是图论中一个经典问题，曾多次出现在信息学竞赛考场上；同时最短路也与实际生活息息相关，比如常用的地图导航涉及的路径规划使用的核心算法就是最短路算法，因此竞赛生需要牢牢掌握最短路的相关算法。

2 最短路问题

最短路问题主要是研究在带权连通图中，一个结点到达另一个结点的所有路径中找权值和最小的一条路径。所谓带权连通图指图中任意一条边是带有权值的，并且任意两结点之间至少存在一条路径。

在信息学竞赛中，主要给学生讲解四种常用的求解最短路问题的算法，这四种算法各有优劣，对于不同的竞赛题目，推荐学生选择较优的算法解题。

3 最短路算法

3.1 Floyed-Warshall算法

Floyed-Warshall算法又称弗洛伊德最短路算法，该算法是利用动态规划算法的思想求解最短路问题的算法，复杂度为O（n3）。调用一次Floyed-Warshall算法就可以直接求出一个n阶图的任意两个结点之间的最短路，称之为多源最短路算法。

优点：学生容易理解和记忆，代码实现简单；可以处理存在负边权的图；有向图和无向图都可适用。

缺点：时间复杂度高，不适合大数据求解；必须用邻接矩阵存储数据，内存占用大，适用于稠密图。

算法思想：设一个图的信息用邻接矩阵二维g数组存储，如果结点i和结点j直接联通，g［i］［j］等于i和j的边权，如果i和j不连通，则g［i］［j］等于无穷大。

设dis［i］［j］［k］表示i到j的路径上的中间结点只经过1～k时，i到j为最短路距离。

最短路经过k:dis［i］［j］［k］=dis［i］［k］［k-1］+dis［k］［j］［k-1］。

最短路不经过k:dis［i］［j］［k］=dis［i］［j］［k-1］综上，状态转移方程为dis［i］［j］［k］=min(dis［i］［j］［k-1］，dis［i］［k］［k-1］+dis［k］［j］［k-1］)。

分析以上状态转移方程不难发现，在状态转移过程中，k的值是不断递增的，所以可以进行空间优化，直接去掉第三个维度k，用一个二维数组dis［i］［j］就可以完成最短路径的计算。

边界条件：dis［i］［j］=g［i］［j］。

核心代码1如图1所示。i、j、k三者不要重复相等。

图1 核心代码

Floyed-Warshall算法的变形主要作用是判断无权图中的两结点是否连通。

设邻接矩阵bool数组g［i］［j］=true表示i和j直接连通，g［i］［j］=false表示i和j不直接连通。

边界条件：dis［i］［j］=g［i］［j］。

核心代码2如图2所示。

图2 核心代码2

3.2 Dijkstra算法

Dijkstra算法又称迪杰斯特拉算法。该算法是利用贪心算法的思想求解最短路问题的算法，复杂度为O（n2）。调用一次Dijkstra算法就可以直接求出一个已定的结点到图中其他所有结点的最短路径，称之为单源最短路算法。

优点：算法思路简明、容易理解；时间复杂度低，如果加堆优化复杂度可达O（n*logn）。

缺点：不能处理存在负边权的图。

算法思想：设已知带权图G=(V，E)，其中V是结点的集合，E是边的集合，求解v0到其他所有结点的最短路，用dis［i］表示v0到i的最短路。该算法采用贪心策略，将结点分到两个集合S、U中，S集中的结点v已经求出了最短路dis［v］，并且不再更新值。对于U中的结点u，dis［u］不一定是v0到u的最短路，还需要进一步计算。计算的方式是每次从U中选择一个dis［u］最小的结点u，把u加入S中。并用u作为中间结点，更新U中其他结点u1的dis［u1］。

算法步骤：①初始化dis［v0］=0，其他dis［i］=+∞。②执行n次如下操作，每次确定一个结点v的最短路dis［v］。选择未被标记的结点k并且dis［k］最小；标记k，可以用一个bool数组vis［k］=true标记；以k为中间点，修改其余未被标记的点的u的最短路的值dis［u］。核心代码【版本1】：邻接矩阵O（n2），如图3所示。

图3 核心代码【版本1】

朴素版Dijkstra算法的时间复杂度达到O（n2）。

核心代码【版本2】：堆（优先队列）+邻接表优化O（nlogn），如图4所示。

图4 核心代码【版本2】

3.3 Bellman-Ford算法

Bellmaxn-Ford算法是求解包含负边权的单源最短路问题的一种算法，算法时间复杂度为O（nm），因为Dijkstra算法不能解决有负边权的最短路，因此Bellman-Ford比Dijkstra算法适用范围更广一些。

优点：可以处理边权为负值的图，思路简洁易掌握。

缺点：时间复杂度高，无法处理存在负权回路情况。

算法思想：与Dijkstra算法相同，求解v0到其他所有结点的最短路，用dis［i］表示v0到i的最短路。接下来对所有边进行松弛操作，求出每个点到v0的最短距离；然后遍历所有边的两个端点，如果存在从源点可达的负环即dis［u］+g［u］［v］

算法步骤：初始化dis数组为正无穷，dis［s］=0；进行n-1次操作，每一次遍历所有边，对于每条边u-v，如果以u为中介点可以使dis［v］更小，就更新dis［v］；检验图中是否存在负环，即遍历所有边判断dis［u］+g［u］［v］

Bellman-Ford算法下核心代码如图5所示。

图5 Bellman-Ford算法下核心代码

3.4 SPFA算法

虽然Bellman-Ford算法思路简洁，但是时间复杂度却很高，在比赛中不太实用。仔细分析可以发现，在Bellman-Ford算法中，只有当起始点u的dis［u］值发生改变时，其出边对应的终点v的dis［v］值才可能发生改变，基于这一点，可以利用队列对Bellman-Ford算法进行优化，优化后得到的就是SPFA算法，算法时间复杂度为O（km），m为图的边数，k为所有顶点入队的平均次数，在很多情况k是小于等于2的，因此在大多数时候SPFA算法性能都很好。

优点：时间复杂度低，可以处理存在负边权的情况。

缺点：不能处理负环。

算法思想：基于Bellman-Ford算法，可以发现只有当某个点u到源点的最短距离dis［u］发生改变，才可能影响从u出发的边到达的终点v的dis［v］值。因此，可以建立一个队列，每次取出队头节点u，然后遍历u所有的出边进行松弛操作，如果dis［u］+g［u］［v］

算法步骤：初始化dis数组为正无穷，dis［s］=0，num数组初始化为0，num［s］=1，将源点s入队，将s的入队标记flag［s］设为true；当队列不为空时，取出队头结点u，更改u的标记为false；遍历u的所有出边进行松弛操作，如果以u为中介点可以使dis［v］更小，就更新dis［v］，如果v被更新且v不在队列中，那么将v入队，更改v的入队标记，同时num［v］++，如果num［v］>=n，则返回false。SPFA算法下核心代码如图6所示。

图6 SPFA算法下核心代码

4 最短路算法的选择

对于不同的竞赛题目，学生可以分析题意，将题目抽象成图后，根据图的性质：求单源最短路还是多源最短路、稀疏图还是稠密图、是否存在负权边等来选择对应的算法，例如稀疏图（无论是否存在负权边），建议采用SPFA算法，效率会更高，而对于稠密图可以分情况讨论，不存在负权时建议使用Dijkstra算法，如果对时间要求不是太严格，也可以采用Floyd算法；具体问题还需具体分析，以上建议只是一个参考。最短路问题是许多更深层次图论问题的基础，学好最短路算法，可为后续学习更复杂的图论算法做准备。