最短路径快速算法

给定一个有向带权图${\displaystyle G=(V,E)}$和一个源点${\displaystyle s}$，SPFA算法可以计算从${\displaystyle s}$到图中每个节点${\displaystyle v}$的最短路径。其基本思路与 Bellman-Ford 算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。但相较于 Bellman-Ford 算法，SPFA算法的改进之处在于它并不盲目地尝试所有节点，而是维护一个备选的节点队列，并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

下面是这个算法的伪代码。[5]这里的${\displaystyle Q}$是一个备选节点的先进先出队列，${\displaystyle w(u,v)}$ 是边${\displaystyle (u,v)}$的权值。

一个基于欧氏几何距离的SPFA算法。红线是当前状态下的各条最短路径。蓝线表示松弛发生的地方，也即通过在${\displaystyle Q}$中用节点${\displaystyle u}$连接${\displaystyle v}$可以给出一条从源点到${\displaystyle v}$更短的路径

 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

对于无向图，可通过将每个无向边视作两条有向边以采用 SPFA 算法。

下面是一种触发该算法低性能表现的数据构造方式。假设要求从节点1到节点${\displaystyle n}$的最短路径。对于整数${\displaystyle 1\leq i<n}$，考虑添加边${\displaystyle (i,i+1)}$并令其权为一个随机的小数字（于是最短路应为1-2-...-${\displaystyle n}$），同时随机添加${\displaystyle 4n}$条其他的权较大的边。在这种情况下，SPFA算法的性能表现将会非常低下。[1]

由于SPFA算法本质上依然被认为是Bellman-Ford算法的一个特例，SPFA算法的最差复杂度依然被认为是${\displaystyle O(|V|\cdot |E|)}$，其中${\displaystyle |V|}$为边数，${\displaystyle |E|}$为点数。[1]

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

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

 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

• 夏正冬; 卜天明; 张居阳. . 《计算机科学》. 2014, 41 (6): 180–184 [2020-11-17].