我们相距十万光年

晨露正葱茏,来日盛景定无穷

11/8
16:19
ACM-ICPC

单源最短路 SSSP

单源最短路,英文是Single Source Shortest Path,通常缩写为SSSP。常见的单源最短路算法有Floyd,Dijkstra,SPFA等。

<1> Floyd算法

Floyd算法,又称Floyd-Warshall算法。在严格意义上来说,这种算法其实不是单源最短路,而是多元最短路,即任意两点之间距离最短。
Floyd算法的思想来自于动态规划(Dynamic Programming),它的时间复杂度是O(n ^ 3),复杂度还是比较高的。
Floyd算法的实现使用的是邻接矩阵。C++代码如下:

<2> SPFA 算法

SPFA 算法的全称是 Shortest Path Faster Algorithm,是由西南交通大学的段凡丁教授提出的算法。该算法的实质是对 Bellman-Ford 算法进行了队列优化。

SPFA 的复杂度理论上是O(nm),但是实测情况下 SPFA 算法的复杂度是 O(RP),还是要谨慎使用。朴素的 SPFA 算法代码如下:

接下来的这种写法是 SPFA 算法的一种优化策略,叫做 SLF(Small Label First),采用了 STL 中的双端队列 deque,将较小的元素直接插入队首。代码实现如下:

SPFA 算法很重要的一个用处就是判断图中是否存在有负环,只需要额外开一个数组记录一下某个点进入队列的次数。如果该点进队超过 n 次,即证明有负环。代码如下:

<3> Dijkstra 算法

Dijkstra 算法是解决单源最短路问题的经典算法,也是最稳定的算法,适用于没有负边权的情况,其复杂度为O(n ^ 2)。经过二叉堆(Binary Heap)优化之后,其复杂度可以降为O((m + n)logn)。据说用斐波那契堆(Fibonacci Heap)优化效果更佳,可以把复杂度降为O(n + mlogm),可惜身为蒟蒻的我并不会写。

下面的代码是 Dijkstra 算法的二叉堆优化写法,二叉堆的实现使用的是 STL 中的优先队列 priority_queue。代码如下:

有些时候,题目中给出的图是无向图,那么我们就需要建双向边。代码如下:

 

Copyright © 2018 All Rights Reserved.