Shortest Path Faster Algorithm

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. 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; the same algorithm was rediscovered in 1994 by Fanding Duan. 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. 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; the same algorithm was rediscovered in 1994 by Fanding Duan. Given a weighted directed graph G = ( V , E ) {displaystyle G=(V,E)} and a source vertex s {displaystyle s} , the SPFA algorithm finds the shortest path from s {displaystyle s} , to each vertex v {displaystyle v} , in the graph. The length of the shortest path from s {displaystyle s} , to v {displaystyle v} is stored in d ( v ) {displaystyle d(v)} for each vertex v {displaystyle v} .