SPFA优化
· 阅读需 1 分钟
对于较为稀疏且数据卡了的图,按理来说是过不去的
但是我们不讲理!!!
我们需要使用对于的两个优化:(Small Label First)和(Large Label Last)
即改用双端队列,每次插入新的点前先和队首比较一下,若更优则放在队首,否则放在队尾
即维护数列平均值,弹出队首后如果大于平均值则放到队尾,重复直到队首小于等于平均值
两个都是基于贪心的思想进行的优化且因为两个不冲突,所以可以连同一起使用,能够通过很多原本过不了的数据点
但是遇到一些稀疏且无负权的图,还是Djistra最保险
