Shortest Path Faster Algorithm: Finding shortest path from a node


(Team) #1
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.

The credit for SPFA algorithm goes to Fanding Duan.

Worst case time complexity: Θ(VE)

Space complexity: Θ(V)
This is a companion discussion topic for the original entry at