最短路径快速算法（），国际上普遍认为是带有佇列最佳化的Bellman-Ford 算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 演算法相同，因此在非负边权的图中，使用堆优化的Dijkstra 算法效率可能优于SPFA。 SPFA首先在1959年由作为广度优先搜索的扩展发表，相同算法在1994年由段凡丁重新发现。
算法
给定一个有向带权图 G=(V,E) 和一个源点 s ，SPFA可以计算从 s 到图中每个节点 v 的最短路径。其基本思路与 Bellman-Ford 算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。但相较于 Bellman-Ford 算法，SPFA的先进之处在于它并不盲目地尝试所有节点，而是维护一个备选的节点队列，并且仅有节点被松弛后才会将其放入队列中。整个流程不断重复，直至没有节点可以被松弛。
下面是这个算法的伪代码。这里的 Q 是一个备选节点的先进先出队列， w(u,v) 是边 (u,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) n的最短路径。对于整数 1\leq i，考虑添加边 (i,i+1) 并令其权为一个随机的小数字（于是最短路应为1-2-...- n ），同时随机添加 4n 条其他的权较大的边。在这种情况下，SPFA的性能表现将会非常低下。
SPFA本质上依然被认为是Bellman-Ford算法的一个特例，因此一般认为SPFA的最差复杂度是O(|V|\cdot|E|)，其中|V|为点数，|E|为边数。
优化技巧
SPFA的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。事实上，如果 Q 是一个优先队列，则这个算法将很类似于Dijkstra 算法。然而尽管这一算法中并没有用到优先队列，仍有多种可用的技巧可以用来提升队列的质量，借此能够提高平均性能（但仍无法提高最坏情况下的性能）。其中，最著名的两种技巧通过重新调整 Q 中元素的顺序从而使得更靠近源点的节点能够被更早地处理。因此一旦实现了这两种技巧， Q 将不再是一个先进先出队列，而更像一个链表或双端队列。
距离小者优先 （Small Label First(SLF)）（由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出)。在伪代码的第十一行，将总是把 v 压入队列尾端修改为比较 d(v) 和 d\big(\text{front}(Q)\big) ，并且在 d(v) 较小时将 v 压入队列的头端。这一技巧的伪代码如下（这部分代码插入在上面的伪代码的第十一行后）：
procedure Small-Label-First(G, Q)
if d(back(Q)) x
u := pop front of Q
push u to back of Q
参考文献
扩展阅读
*
评论 (0)