Shortest path faster algorithm

It has been suggested that this article be merged into Bellman–Ford algorithm. (Discuss) Proposed since April 2024.

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (November 2023) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Shortest path faster algorithm" – news · newspapers · books · scholar · JSTOR (November 2023) (Learn how and when to remove this message) (Learn how and when to remove this message)

The Shortest Path Faster Algorithm (SPFA) is an enhanced version of the Bellman–Ford algorithm that computes single-source shortest paths in a weighted directed graph. The algorithm performs optimally on sparse random graphs, particularly those with negative-weight edges.^[1][2][3] The worst-case complexity of SPFA is equivalent to that of the Bellman–Ford. Dijkstra's algorithm is preferred for graphs with nonnegative edge weights.^[4]

SPFA was first introduced by Edward F. Moore in 1959, as a generalization of the breadth-first search;^[5] SPFA is Moore's “Algorithm D.” The term “Shortest Path Faster Algorithm (SPFA)” was coined by Fanding Duan, a Chinese researcher who rediscovered the algorithm in 1994.^[6]

Algorithm[edit]

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

SPFA improves upon the Bellman-Ford algorithm by selectively using vertices to relax their adjacent vertices. Instead of processing all vertices indiscriminately, SPFA maintains a queue of candidate vertices and only adds a vertex to the queue if it has been relaxed, continuing this process until no further vertices can be relaxed.

Below is the pseudocode for the algorithm.^[7] Here ${\displaystyle Q}$ is a first-in, first-out queue of candidate vertices, and ${\displaystyle w(u,v)}$ is the edge weight between ${\displaystyle (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    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 treating each undirected edge as two directed edges of opposite directions.

Proof of correctness[edit]

It is feasible to demonstrate that the algorithm consistently identifies the shortest path.

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

Proof: To demonstrate that if ${\displaystyle dist[w]>dist[u]+w(u,w)}$ for any two vertices ${\displaystyle u}$ and ${\displaystyle w}$ when the condition is checked, ${\displaystyle u}$ is in the queue. We use induction based on the number of iterations of the loop that have occurred. Initially, this holds before the loop starts: If ${\displaystyle u\not =s}$, then relaxation is not possible; relaxation is possible from ${\displaystyle u=s}$, and this vertex is added to the queue immediately before the while loop begins. Inside the loop, a vertex ${\displaystyle u}$ is popped and used to relax all its neighbors, if possible. Immediately after that iteration of the loop, ${\displaystyle u}$ is not capable of causing any more relaxations (and does not need to be in the queue anymore). However, the relaxation by ${\displaystyle x}$ might cause some other vertices to become capable of causing relaxation. If there exists some vertex ${\displaystyle x}$ such that ${\displaystyle dist[x]>dist[w]+w(w,x)}$ before the current loop iteration, then ${\displaystyle w}$ is already in the queue. If this condition becomes true during the current loop iteration, then either ${\displaystyle dist[x]}$ increased, which is impossible, or ${\displaystyle dist[w]}$ decreased, implying that ${\displaystyle w}$ was relaxed. But after ${\displaystyle 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 to 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 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.^[8]

Complexity[edit]

Experiments indicate that the average time complexity of SPFA is ${\displaystyle O(|E|)}$ on random graphs, and the worst-case time complexity is ${\displaystyle \Omega (|V|\cdot |E|)}$, which is equal to that of the Bellman-Ford algorithm.^[1][9]

Optimization techniques[edit]

The performance of the algorithm is significantly influenced by the order in which candidate vertices are used to relax other vertices. Although ${\displaystyle Q}$ is not a priority queue, two techniques are often used to enhance the quality of the queue, thereby improving the average-case performance (but not the worst-case performance). Both techniques reorder the elements in ${\displaystyle Q}$ so that vertices closer to the source are processed first. Therefore, when implementing these techniques, ${\displaystyle 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 of the above pseudocode, instead of always pushing the vertex ${\displaystyle v}$ to the end of the queue, we compare ${\displaystyle d(v)}$ to ${\displaystyle d{\big (}{\text{front}}(Q){\big )}}$, and insert ${\displaystyle v}$ to the front of the queue if ${\displaystyle d(v)}$ is smaller. The pseudo-code for this technique is (after pushing ${\displaystyle 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[edit]