最短路径快速算法 （英語：Shortest Path Faster Algorithm (SPFA) ），国际上一般认为是带有队列优化的Bellman-Ford 算法 ，一般仅在中国大陆被称为SPFA ，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。[ 1] Dijkstra 算法 效率可能优于SPFA。[ 2] Edward F. Moore 广度优先搜索 的扩展发表[ 3] [ 4]
给定一个有向带权图
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
s
{\displaystyle s}
s
{\displaystyle s}
v
{\displaystyle v}
下面是这个算法的伪代码。[ 5]
Q
{\displaystyle Q}
w
(
u
,
v
)
{\displaystyle w(u,v)}
(
u
,
v
)
{\displaystyle (u,v)}
一个基于欧氏几何距离的SPFA算法。红线是当前状态下的各条最短路径。蓝线表示松弛发生的地方，也即通过在
Q
{\displaystyle Q}
u
{\displaystyle u}
v
{\displaystyle v}
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到节点
n
{\displaystyle n}
1
≤ ≤ -->
i
<
n
{\displaystyle 1\leq i<n}
(
i
,
i
+
1
)
{\displaystyle (i,i+1)}
n
{\displaystyle n}
4
n
{\displaystyle 4n}
[ 1]
SPFA算法本质上依然被认为是Bellman-Ford算法的一个特例，因此一般认为SPFA算法的最差复杂度是
O
(
|
V
|
⋅ ⋅ -->
|
E
|
)
{\displaystyle O(|V|\cdot |E|)}
|
V
|
{\displaystyle |V|}
|
E
|
{\displaystyle |E|}
[ 1]
NOI 2018中，出题人使用特殊构造图卡到SPFA算法的最坏情况，并在讲题时在幻灯片上打出关于“SPFA它死了”的字样，导致现今很多中国大陆OI题目都会构造特殊数据卡掉SPFA，于是关于SPFA已死的说法广泛流传于中国大陆。[原創研究？]
SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。事实上，如果
Q
{\displaystyle Q}
Q
{\displaystyle Q}
Q
{\displaystyle Q}
距离小者优先 （Small Label First (SLF )）（由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出)。在伪代码的第十一行，将总是把
v
{\displaystyle v}
d
(
v
)
{\displaystyle d(v)}
d
(
front
(
Q
)
)
{\displaystyle d{\big (}{\text{front}}(Q){\big )}}
d
(
v
)
{\displaystyle d(v)}
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
夏正冬; 卜天明; 张居阳. SPFA算法的分析及改进 . 《计算机科学》. 2014, 41 (6): 180–184 [2020-11-17 ] . （原始内容存档 于2020-12-08）. 
