Shortest Path Faster Algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.[1] However, the worst-case complexity of SPFA is the same as that of Bellman–Ford, so for graphs with nonnegative edge weights Dijkstra's algorithm is preferred. The SPFA algorithm was first published by Edward F. Moore in 1959, as a generalization of breadth first search;[2] the same algorithm was rediscovered in 1994 by Fanding Duan.[3]

Algorithm[edit]

Given a weighted directed graph and a source vertex , the SPFA algorithm finds the shortest path from , to each vertex , in the graph. The length of the shortest path from , to is stored in for each vertex .

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.[4] Here is a first-in, first-out queue of candidate vertices, and is the edge weight of .

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 with a node in , which gives a shorter path from the source to .
 procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex vs 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 also be applied to an undirected graph by replacing each undirected edge with two directed edge of opposite directions.

Proof of correctness[edit]

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[5].

Running time[edit]

The worst-case running time of the algorithm is , just like the standard Bellman-Ford algorithm.[1] Experiments suggest that the average running time is [3], and indeed this is true on random graphs, but it is possible to construct sparse graphs where SPFA runs in time like the usual Bellman-Ford algorithm[6].

Optimization techniques[edit]

The performance of the algorithm is strongly determined by the order in which candidate vertices are used to relax other vertices. In fact, if is a priority queue, then 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 so that vertices closer to the source are processed first. Therefore, when implementing these techniques, 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. In line 11, instead of always pushing vertex to the end of the queue, we compare to , and insert to the front of the queue if is smaller. The pseudo-code for this technique is (after pushing 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[edit]

  1. ^ a b About the so-called SPFA algorithm
  2. ^ 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. SPFA is Moore's “Algorithm D”.
  3. ^ a b Duan, Fanding (1994), "关于最短路径的SPFA快速算法", 西南交通大学学报 [Journal of Southwest Jiaotong University], 29 (2): 207–212
  4. ^ http://codeforces.com/blog/entry/16221
  5. ^ "Shortest Path Faster Algorithm". wcipeg.
  6. ^ Ke, Yang. "Worst test case for SPFA".