Shortest Path Faster Algorithm
The Shortest Path Faster Algorithm (SPFA) is a shortest path algorithm whose origin is unknown[see references]. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the average case, it is likely to outperform Bellman-Ford (although not Dijkstra's). In theory, this should lead to an improved version of Johnson's algorithm as well.
The algorithm
References
Details of the algorithm were obtained from code written by Gelin Zhou (University of Waterloo) who himself attributes the algorithm to a slide presented in a computer science class at MIT. The contributors to this article are unable to find a reference to it in the informatics literature.
