Bellman–Ford algorithm: Difference between revisions

Revision as of 01:39, 21 May 2025

Revision as of 02:26, 21 May 2025

Line 132:

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_f'' and ''E_b'') 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|2023}}, at [[Georgetown University]], created an improved algorithm that with high probability, runs in <math>\tilde O(|V|^\frac{8}{9}\cdot |E|)</math> [[Bigtime complexity|time]]. Here, the <math>\tilde O</math> is a variant of [[big O notation|time]] that hides logarithmic factors.

== Notes ==