Shortest path faster algorithm
The Shortest Path Faster Algorithm, often abbreviated as SPFA, computes single-source shortest paths in a weighted directed graph. The graph is allowed to have negative edge weights, but not negative cycles. The algorithm is an improvement over the Bellman–Ford algorithm. The algorithm was published in 1994 by Fanding Duan.[1] The algorithm is believed to work well on random sparse graphs and graphs that contains negative weight edges.[2] However, for situations where Dijkstra's algorithm is applicable, it is preferred because SPFA is not stable.[3]
Algorithm
Given a directed graph G = (V, E) without negative cycles, the SPFA algorithm maintains a queue Q of vertices that are candidates to relax other vertices. Initially, only the source vertex s is in the queue.
Below is the pseudo-code of the algorithm.[4]
procedure Shortest-Path-Faster-Algorithm(G, s)
Initialize-Single-Source(G, s)
push s into Q
while Q is not empty
pop u from Q
for each vertex v adjacent to u
if d(u) + w(u, v) < d(v) then
d(v) := d(u) + w(u, v)
if v is not in Q then
push v into Q
Optimize-Queue(G, Q)
procedure Initialize-Single-Source(G, s)
for each vertex v ≠ s in G
d(v) := ∞
d(s) := 0
procedure Optimize-Queue(G, Q)
; see section Optimization Techniques below
The algorithm can also be applied to an undirected graph by replacing each undirected edge with two directed edge of opposite directions.
Proof of Correctness
http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm
Average-case Performance
For a random graph, the empirical average time complexity is O(|E|).[4][1]
Worst-case Performance
Following is a way to construct a data to defeat this algorithm (without queue optimization???).[2] Suppose you want the shortest path from vertex 1 to vertex n, then we can add edge (i, i + 1) with a small random weight for 1 <= i < n (thus the shortest path should be 1-2-...-n), and randomly add 4n other heavy edges. For this case, the so-called SPFA algorithm will be very slow.
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, than the algorithm pretty much resembles Dijkstra's. However, since a priority queue is not used here, two techniques are sometimes employed to improve the quality of the queue.
Small Label First (SLF) technique: in line 10, when we push vertex v into the queue, let v0 be the first element in the queue. If d[v] < d(v0), then insert v to the beginning of the queue. Otherwise, append v to the end of the queue. This technique tends to process nodes that are closer to the source first. Its idea is similar to that of Dijkstra, except that it only compares with the front node.
procedure Small-Label-First(G, Q)
u := front(Q)
v := back(Q)
if d(v) < d(u) then
pop_back(Q)
push_front(Q, v)
Large Label Last (LLL) technique: after step 10, we find the first element that is smaller than the average.
procedure Large-Label-Last(G, Q)
x := average of d(v) for all v in Q
while true
u := first element in Q
if d(u) ≤ x then exit while
pop u from Q
push u to Q