Shortest Path Faster Algorithm

Algorithm

Given a weighted directed graph G = (V, E) and a source vertex s, the SPFA algorithm 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.

The basic idea of SPFA is the same as Bellman–Ford algorithm in that each vertex is used as a candidate to relax its adjacent vertices. The improvement over the latter is that 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. This process repeats until no more vertex 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).

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

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|).

Worst-case performance

Following is a way to construct a data to defeat this algorithm (without queue optimization???). Suppose one wants 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, which in turn improves the average-case performance (but not the worst-case performance). Both techniques rearranges 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 queue, but rather a normal doubly linked list or double-ended queue.

Small Label First (SLF) technique (first proposed by Bertsekas in Networks, Vol. 23, 1993, pp. 703-709). In line 11, instead of always pushing vertex v to the end of the queue, we compare d(v) to d(front(Q)), 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 (first proposed by Bertsekas, Guerriero, and Musmanno in JOTA, Vol. 88, 1996, pp. 297-320). 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