OceanEye's Blog

是时候表演真正的技术了!

@OceanEye7月前

04/7
23:56
OI

SPFA的几个优化

SPFA自问世以来,就一直活跃在奥赛各界。因为其极其优化的复杂度和很短的编写代码,各大OI主流媒体都称其为最短路利器。但是,有人闲来无聊之时,在举办模拟赛的时候,会用大量的功夫用于卡掉普通的SPFA(个人觉得比较蛋疼,按理来说是不应该阻碍新技术的推广)。使用我收集了几个比较常见的优化,可以优化SPFA,更重要的是,这个就如随机化快排一般,使SPFA不太会受数据的限制。

1.循环队列

循环队列是因为SPFA的另一个优化,对于队列中已经存在的点,在SPFA的拓展过程中,这个点是不能重复加入的。这样的话,最坏的情况是所有的点都在队列中,队列长度最多与N同级别。这时,可以用循环队列保证队列的长度于N同级别。实现方法就是在head,tail的更新过程中,如果发现大于队列最大允许长度,那么就将其变为1。因为head,tail每次最多加1,所以这样做就可以了。需要注意的是,SPFA的结束条件要变为Head=Tail,有些同学喜欢写Head>=Tail,如果写循环队列的话,这样写是有可能出错的。

2.SLF即Small Label First策略。

实现的方法很简单,即当你要向队列中添加节点的时候,先将其与队首元素比较,如果其比队首元素要优(当前已知的最短距离更小一些),那么将其放在队首的位置,否则放到队尾。这样保证较小距离的节点优先得到拓展。可以使SPFA更快的结束。

3.LLL即Large Label Last 策略。

表示不会,请移步这里

4.还有一个不知名的优化(没有验证过)

若当前元素没有目标节点优,则不更新。

以上。


转自:http://www.blogbus.com/oibltx-logs/125657995.html

 

SPFA的几个优化