我们相距十万光年

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

11/8
16:19
ACM-ICPC

单源最短路 SSSP

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

<1> Floyd 算法

Floyd 算法在严格意义上来说其实不是单源最短路,而是任意两点之间距离最短。它的复杂度是O(n ^ 3),复杂度还是比较高的。

Floyd 算法的实现使用的是邻接矩阵。代码如下:

<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.