0: 基本概念
- ** 松弛操作：更新节点的值 ： v_end=min（v_end, v_source +v_side）
v_end：表示边的终点（需要更新的节点值）；
v_source: 表示 边的源点；
v_source：表示边的终点
注：若节点值无变化，则表示松弛不成功** -
队列 ： 先进先出
image.png
一、用武之地：
- 给定的图G存在负权边，但不存在负权回路
二、参考此链接
直接从实验方法看起
三、SPFA算法有两个优化算法 SLF 和 LLL：
SLF：
Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。
LLL：
Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。
引用网上资料，SLF 可使速度提高 15 ~ 20%；
网友评论