Content deleted Content added
m →Secondary sources: Updating Cormen reference to 4th edition |
m →Improvements: Updating reference to Cormen edition 4 (instead of edition 2) |
||
Line 132:
A variation of the Bellman–Ford algorithm known as [[Shortest Path Faster Algorithm]], first described by {{harvtxt|Moore|1959}}, reduces the number of relaxation steps that need to be performed within each iteration of the algorithm. If a vertex ''v'' has a distance value that has not changed since the last time the edges out of ''v'' were relaxed, then there is no need to relax the edges out of ''v'' a second time. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to a constant-factor savings in time for [[dense graph]]s.
{{harvtxt|Yen|1970}} described another improvement to the Bellman–Ford algorithm. His improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into two subsets. The first subset, ''E<sub>f</sub>'', contains all edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' < ''j''; the second, ''E<sub>b</sub>'', contains edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' > ''j''. Each vertex is visited in the order {{math|''v<sub>1</sub>'', ''v<sub>2</sub>'', ..., ''v''<sub>{{!}}''V''{{!}}</sub>}}, relaxing each outgoing edge from that vertex in ''E<sub>f</sub>''. Each vertex is then visited in the order {{math|''v''<sub>{{!}}''V''{{!}}</sub>, ''v''<sub>{{!}}''V''{{!}}−1</sub>, ..., ''v''<sub>1</sub>}}, relaxing each outgoing edge from that vertex in ''E<sub>b</sub>''. Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match the correct shortest path distances: one from ''E<sub>f</sub>'' and one from ''E<sub>b</sub>''. This modification reduces the worst-case number of iterations of the main loop of the algorithm from {{math|{{abs|''V''}} − 1}} to <math>|V|/2</math>.<ref>Cormen et al.,
Another improvement, by {{harvtxt|Bannister|Eppstein|2012}}, replaces the arbitrary linear order of the vertices used in Yen's second improvement by a [[random permutation]]. This change makes the worst case for Yen's improvement (in which the edges of a shortest path strictly alternate between the two subsets ''E<sub>f</sub>'' and ''E<sub>b</sub>'') very unlikely to happen. With a randomly permuted vertex ordering, the [[expected value|expected]] number of iterations needed in the main loop is at most <math>|V|/3</math>.<ref name=Sedweb>See Sedgewick's [http://algs4.cs.princeton.edu/44sp/ web exercises] for ''Algorithms'', 4th ed., exercises 5 and 12 (retrieved 2013-01-30).</ref>
| |||