# 最短路径快速算法

（重定向自SPFA算法

## 算法

SPFA总的期望时间复杂度为$O(nlognlog(m/n)+m)$ ，基于实验获得的平均时间复杂度为$O(2|E|)$

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


## 正确性证明

We will prove that the algorithm never computes incorrect shortest path lengths.

Lemma: Whenever the queue is checked for emptiness, any vertex currently capable of causing relaxation is in the queue.
Proof: We want to show that if  for any two vertices  and  at the time the condition is checked,  is in the queue. We do so by induction on the number of iterations of the loop that have already occurred. First we note that this certainly holds before the loop is entered: if , then relaxation is not possible; relaxation is possible from , and this is added to the queue immediately before the while loop is entered. Now, consider what happens inside the loop. A vertex  is popped, and is used to relax all its neighbors, if possible. Therefore, immediately after that iteration of the loop,  is not capable of causing any more relaxations (and does not have to be in the queue anymore). However, the relaxation by  might cause some other vertices to become capable of causing relaxation. If there exists some  such that  before the current loop iteration, then  is already in the queue. If this condition becomes true duringthe current loop iteration, then either  increased, which is impossible, or decreased, implying that  was relaxed. But after  is relaxed, it is added to the queue if it is not already present.
Corollary: The algorithm terminates when and only when no further relaxations are possible.
Proof: If no further relaxations are possible, the algorithm continues to remove vertices from the queue, but does not add any more into the queue, because vertices are added only upon successful relaxations. Therefore the queue becomes empty and the algorithm terminates. If any further relaxations are possible, the queue is not empty, and the algorithm continues to run.

The algorithm fails to terminate if negative-weight cycles are reachable from the source. See here for a proof that relaxations are always possible when negative-weight cycles exist. In a graph with no cycles of negative weight, when no more relaxations are possible, the correct shortest paths have been computed (proof). Therefore in graphs containing no cycles of negative weight, the algorithm will never terminate with incorrect shortest path lengths.

## 优化技巧

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

 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


 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


## 参见

1. About the so-called SPFA algorithm
2. ^
3. ^ Moore, Edward F. The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching. Harvard University Press: 285–292. 1959. SPFA is Moore's “Algorithm D”.
4. ^ SPFA算法详解. Leo Zhao 's blog. [2018-10-13].
5. ^ Pacific. 如何卡spfa？ - Pacific的回答 - 知乎. 2018-03-09 [2019-07-23].
6. ^ http://codeforces.com/blog/entry/16221