Editing Shortest Path Faster Algorithm

The '''Shortest Path Faster Algorithm''' (SPFA) is a [[shortest path]] algorithm whose origin is unknown<sup>[see references]</sup>. 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.