跳到主要内容

SPFA优化

· 阅读需 1 分钟

对于较为稀疏且数据卡了SPFASPFA的图,按理来说是过不去的

但是我们不讲理!!!

我们需要使用对于SPFASPFA的两个优化:SLFSLF(Small Label First)和LLLLLL(Large Label Last)

SLFSLF即改用双端队列,每次插入新的点前先和队首比较一下,若更优则放在队首,否则放在队尾

LLLLLL即维护数列平均值,弹出队首后如果大于平均值则放到队尾,重复直到队首小于等于平均值

两个都是基于贪心的思想进行的优化且因为两个不冲突,所以可以连同一起使用,能够通过很多原本SPFASPFA过不了的数据点

但是遇到一些稀疏且无负权的图,还是Djistra最保险