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 published in 1994 by Fanding Duan. … Shortest Path Faster Algorithm (SPFA)

# If you did not already know: “Shortest Path Faster Algorithm (SPFA)”

**13**
*Sunday*
Sep 2015

Posted What is ...

in