31-SPFA-detail

The Shortest Path Faster Algorithm (SPFA) is an improved version of the Bellman–Ford algorithm that computes single-source shortest paths in a weighted directed graph. The algorithm works well on sparse random graphs, especially those that contain negative-weight edges. The worst-case complexity of SPFA is the same as that of Bellman–Ford, therefore Dijkstra’s algorithm is preferred for graphs with nonnegative edge weights.

SPFA 是 Bellman-Ford 算法的改进版，在带权有向图中计算单源最短路径表现出色，并且非常适合稀疏图，尤其是在包含负权边的图中。 SPFA 的最坏时间复杂度与 Bellman-Ford 相同，

SPFA was first published by Edward F. Moore in 1959, as a generalization of breadth first search; SPFA is Moore’s “Algorithm D.” The name “Shortest Path Faster Algorithm (SPFA)” was given by Fanding Duan, a Chinese researcher who rediscovered the algorithm in 1994.

Algorithm

Given a weighted directed graph $G = (V, E)$ and a source vertex $s$ , SPFA finds the shortest path from $s$ to each vertex $v$ in the graph. The length of the shortest path from $s$ to $v$ is stored in $d(v)$ for each vertex $v$ .

SPFA is similar to the Bellman-Ford algorithm in that each vertex is used as a candidate to relax its adjacent vertices. However, instead of trying all vertices blindly, SPFA maintains a queue of candidate vertices and adds a vertex to the queue only if that vertex is relaxed, repeating the process until no more vertices can be relaxed.

Below is the pseudo-code of the algorithm. Here $Q$ is a first-in, first-out queue of candidate vertices, and $w(u,v)$ is the edge weight of $(u,v)$ .

A demo of SPFA based on Euclidean distance. Red lines are the shortest path covering (so far observed). Blue lines indicate where relaxing happens, i.e., connecting $v$ with a node $u$ in $Q$ , which gives a shorter path from the source to $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    push _s_ into _Q_
  5    **while** _Q_ is not empty **do**
  6        _u_ := poll _Q_
  7        **for each** edge (_u_, _v_) in _E_(_G_) **do**
  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                    push _v_ into _Q_

The algorithm can be applied to an undirected graph by replacing each undirected edge with two directed edges of opposite directions.

Proof of correctness

It is possible to prove that the algorithm always finds the shortest path.

Lemma: Whenever the queue is checked for emptiness, any vertex currently capable of causing relaxation is in the queue.

Proof: To show that if $dist[w]>dist[u]+w (u, w)$ for any two vertices $u$ and $w$ at the time the condition is checked, $u$ 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 holds before the loop is entered: İf $u\not =s$ , then relaxation is not possible; relaxation is possible from $u=s$ , and this is added to the queue immediately before the while loop is entered. Now, consider what happens inside the loop. A vertex $u$ is popped, and is used to relax all its neighbors, if possible. Therefore, immediately after that iteration of the loop, $u$ is not capable of causing any more relaxations (and does not have to be in the queue anymore). However, the relaxation by $x$ might cause some other vertices to become capable of causing relaxation. If there exists some vertex $x$ such that $dist[x]>dist[w]+w (w, x)$ before the current loop iteration, then $w$ is already in the queue. If this condition becomes true during the current loop iteration, then either $dist[x]$ increased, which is impossible, or $dist[w]$ decreased, implying that $w$ was relaxed. But after $w$ 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.

Complexity

Experiments show that the average time complexity of SPFA is $O(|E|)$ on random graphs, and the worst-case time complexity is $\Omega (|V|\cdot |E|)$ , which is equal to that of Bellman-Ford algorithm.

Optimization techniques

The performance of the algorithm is strongly determined by the order in which candidate vertices are used to relax other vertices. In fact, if $Q$ is a priority queue, then the algorithm resembles Dijkstra’s. However, since a priority queue is not used here, two techniques are sometimes employed to improve the quality of the queue, which in turn improves the average-case performance (but not the worst-case performance). Both techniques rearrange the order of elements in $Q$ so that vertices closer to the source are processed first. Therefore, when implementing these techniques, $Q$ is no longer a first-in, first-out (FIFO) queue, but rather a normal doubly linked list or double-ended queue.

Small Label First (SLF) technique. In line 11, instead of always pushing vertex $v$ to the end of the queue, we compare $d(v)$ to $d{\big (}{\text{front}}(Q){\big )}$ , and insert $v$ to the front of the queue if $d(v)$ is smaller. The pseudo-code for this technique is (after pushing $v$ to the end of the queue in line 11):

**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) technique. After line 11, we update the queue so that the first element is smaller than the average, and any element larger than the average is moved to the end of the queue. The pseudo-code is:

**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_

References

^ Jump up to: a b
^ Pape, U. (1974-12-01). “Implementation and efficiency of Moore-algorithms for the shortest route problem”. Mathematical Programming. 7 (1): 212–222. doi: 10.1007/BF01585517. ISSN 1436-4646.
^ Schrijver, Alexander (2012-01-01). “On the history of the shortest path problem”. ems. press. Retrieved 2023-12-13.
^ Zhang, Wei; Chen, Hao; Jiang, Chong; Zhu, Lin. “Improvement And Experimental Evaluation Bellman-Ford Algorithm”. Proceedings of the 2013 International Conference on Advanced ICT and Education.
^ Moore, Edward F. (1959). “The shortest path through a maze”. Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.
^ Duan, Fanding (1994). “关于最短路径的 SPFA 快速算法 [About the SPFA algorithm]”. Journal of Southwest Jiaotong University. 29 (2): 207–212.
^ “Algorithm Gym :: Graph Algorithms”.
^ “Shortest Path Faster Algorithm”. wcipeg.
^ “Worst test case for SPFA”. Retrieved 2023-05-14.

α–β pruning
A*
- IDA*
- LPA*
- SMA*
Best-first search
Beam search
Bidirectional search
Breadth-first search
- Lexicographic
- Parallel
B*
Depth-first search
- Iterative deepening
D*
Fringe search
Jump point search
Monte Carlo tree search
SSS*

Shortest path

Bellman–Ford
Dijkstra’s
Floyd–Warshall
Johnson’s
Shortest path faster
Yen’s

Minimum spanning tree

Borůvka’s
Kruskal’s
Prim’s
Reverse-delete

List of graph search algorithms

Optimization: Algorithms, methods, and heuristics

🌰Senjl's Digital Garden🐉

Recent writing

Welcome to Senj's Digital Garden

6-文件系统

7-进程间通信与IO重定向

探索