算法

本算法没有经过证明的平均时间复杂度。

给定一个有向带权图和一个源点，SPFA算法计算从到图中每个节点的最短路径。对于每个节点，从到 的最短路径表示为。

SPFA算法的基本思路与贝尔曼-福特算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。相较于贝尔曼-福特算法，SPFA算法的提升在于它并不盲目尝试所有节点，而是维护一个备选节点队列，并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

下面是这个算法的伪代码。这里的是一个备选节点的先进先出队列， 是边的权。

procedure Shortest-Path-Faster-Algorithm(G, s) 1 for each vertex v ≠ s in V(G) 2 d(v) := ∞ 3 d(s) := 0 4 offer s into Q 5 while Q is not empty 6 u := poll Q 7 for each edge (u, v) in E(G) 8 if d(u) + w(u, v) < d(v) then 9 d(v) := d(u) + w(u, v) 10 if v is not in Q then 11 offer v into Q

这个算法也可以通过将每条边换为两条逆向的边来用于无向图。

平均情况下的性能

对于一张随机图，基于实验获得的平均时间复杂度为。

最坏情况下的性能

下面是一种触发该算法低性能表现的数据构造方式（没有队列优化？）。假设要求从节点1到节点的最短路径。对于整数，考虑添加边并令其权为一个随机的小数字（于是最短路应为1-2-...-），同时随机添加条其他的权较大的边。在这种情况下，SPFA算法的性能表现将会非常低下。

优化技巧

SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。事实上，如果是一个优先队列，则这个算法将极其类似于戴克斯特拉算法。然而尽管这一算法中并没有用到优先队列，仍有两种可用的技巧可以用来提升队列的质量，并且借此能够提高平均性能（但仍无法提高最坏情况下的性能）。两种技巧通过重新调整中元素的顺序从而使得更靠近源点的节点能够被更早地处理。因此一旦实现了这两种技巧，将不再是一个先进先出队列，而更像一个链表或双端队列。

距离小者优先 （Small Label First(SLF)）（由Bertsekas在Networks, 第23期, 1993, 页703-709中最先提出)。在伪代码的第十一行，将总是把压入队列尾端修改为比较 和 ，并且在较小时将压入队列的头端。这一技巧的伪代码如下（这部分代码插入在上面的伪代码的第十一行后）：

procedure Small-Label-First(G, Q) if d(back(Q)) < d(front(Q)) then u := pop back of Q push u into front of Q

距离大者置后 （Large Label Last(LLL)）（由Bertsekas、Guerriero、与Musmanno在JOTA, 第88期, 1996, 页297-320最先提出)。在伪代码的第十一行，我们更新队列以确保队列头端的节点的距离总小于平均，并且任何距离大于平均的节点都将被移到队列尾端。伪代码如下：

procedure Large-Label-Last(G, Q) x := average of d(v) for all v in Q while d(front(Q)) > x u := pop front of Q push u to back of Q