博客

一、算法介绍

SPFA算法(Shortest Path Faster Algorithm)是基于Bellman-Ford算法的优化

Bellman-Ford算法复杂度: O(V*E) (V:点个数 E:边个数)

SPFA算法复杂度：O(k*E)  k为所有顶点进队的平均次数

缺点：SPFA的算法时间效率不是很稳定

二、算法思想

Bellman-Ford算法 每次迭代时，每次只有松弛的节点 且 Q中不存在此节点时 才入队列Q

SPFA算法有两个优化算法 SLF 和 LLL：

SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)

否则插入队尾。

LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入

到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。

SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。