Editing Bellman–Ford algorithm (section)

== Improvements ==
The Bellman–Ford algorithm may be improved in practice (although not in the worst case) by the observation that, if an iteration of the main loop of the algorithm terminates without making any changes, the algorithm can be immediately terminated, as subsequent iterations will not make any more changes. With this early termination condition, the main loop may in some cases use many fewer than {{math|{{abs|''V''}}&nbsp;−&nbsp;1}} iterations, even though the worst case of the algorithm remains unchanged. The following improvements all maintain the <math>O(|V|\cdot |E|)</math> worst-case time complexity.

A variation of the Bellman–Ford algorithm 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. This variation can be implemented by keeping a collection of vertices whose outgoing edges need to be relaxed, removing a vertex from this collection when its edges are relaxed, and adding to the collection any vertex whose distance value is changed by a relaxation step. In China, this algorithm was popularized by Fanding Duan, who rediscovered it in 1994, as the "shortest path faster algorithm".<ref>{{cite journal|last=Duan|first=Fanding|year=1994|title=关于最短路径的SPFA快速算法 [About the SPFA algorithm]|journal=Journal of Southwest Jiaotong University|volume=29|issue=2|pages=207–212|url=http://wenku.baidu.com/view/3b8c5d778e9951e79a892705.html}}</ref>

{{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''}}&nbsp;−&nbsp;1}} to <math>|V|/2</math>.<ref>Cormen et al., 4th ed., Problem 22-1, p. 640.</ref><ref name=Sedweb />

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>

{{harvtxt|Fineman|2024}}, at [[Georgetown University]], created an improved algorithm that with high probability runs in <math>\tilde O(|V|^\frac{8}{9}\cdot |E|)</math> [[time complexity|time]]. Here, the <math>\tilde O</math> is a variant of [[big O notation]] that hides logarithmic factors.