Editing Shortest Path Faster Algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | The '''Shortest Path Faster Algorithm''' (SPFA) is a [[ | + | The '''Shortest Path Faster Algorithm''' (SPFA) is a [[shortest path|single-source shortest paths]] 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== | ==The algorithm== | ||
Line 23: | Line 23: | ||
====Proof of correctness==== | ====Proof of correctness==== | ||
− | We will prove that the algorithm | + | We will prove that the algorithm terminates and that it computes the correct shortest path lengths. |
:''Lemma'': Whenever the queue is checked for emptiness, any vertex currently capable of causing relaxation is in the queue. | :''Lemma'': Whenever the queue is checked for emptiness, any vertex currently capable of causing relaxation is in the queue. | ||
Line 31: | Line 31: | ||
:''Proof'': If no further relaxations are possible, the algorithm continues to remove vertices from the queue, but does not add any more into the queue, because vertices are added only upon successful relaxations. Therefore the queue becomes empty and the algorithm terminates. If any further relaxations are possible, the queue is not empty, and the algorithm continues to run. <math>_{_\blacksquare}</math> | :''Proof'': If no further relaxations are possible, the algorithm continues to remove vertices from the queue, but does not add any more into the queue, because vertices are added only upon successful relaxations. Therefore the queue becomes empty and the algorithm terminates. If any further relaxations are possible, the queue is not empty, and the algorithm continues to run. <math>_{_\blacksquare}</math> | ||
− | The algorithm fails to terminate if negative-weight cycles are reachable from the source. See [[Bellman–Ford algorithm#Proof of detection of negative-weight cycles|here]] for a proof that relaxations are always possible when negative-weight cycles exist. In a graph with no cycles of negative weight, when no more relaxations are possible, the correct shortest paths have been computed ([[Shortest path#Relaxation|proof]]). Therefore in graphs containing no cycles of negative weight, the algorithm | + | The algorithm fails to terminate if and only if negative-weight cycles are reachable from the source. See [[Bellman–Ford algorithm#Proof of detection of negative-weight cycles|here]] for a proof that relaxations are always possible when negative-weight cycles exist. In a graph with no cycles of negative weight, when no more relaxations are possible, the correct shortest paths have been computed ([[Shortest path#Relaxation|proof]]). Therefore in graphs containing no cycles of negative weight, the algorithm always terminates and always computes the correct shortest path lengths. |
==References== | ==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. The algorithm almost certainly either originated among or was popularized by Chinese informatics competitors. | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |