Bellman–Ford algorithm: Difference between revisions

Revision as of 23:34, 26 April 2024

Revision as of 00:27, 9 June 2024

Line 131:

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 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. 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_f'', contains all edges (''v_i'', ''v_j'') such that ''i'' < ''j''; the second, ''E_b'', contains edges (''v_i'', ''v_j'') such that ''i'' > ''j''. Each vertex is visited in the order {{math|''v₁'', ''v₂'', ..., ''v''_{{{!}}''V''{{!}}}}}, relaxing each outgoing edge from that vertex in ''E_f''. Each vertex is then visited in the order {{math|''v''_{{{!}}''V''{{!}}}, ''v''_{{{!}}''V''{{!}}−1}, ..., ''v''₁}}, relaxing each outgoing edge from that vertex in ''E_b''. 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_f'' and one from ''E_b''. 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 />