Randomized speedup of the Bellman–Ford algorithm.
M. J. Bannister and
D. Eppstein.
arXiv:1111.5414.
Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan, 2012, pp. 41–47,
doi:10.1137/1.9781611973020.6.
The Bellman–Ford algorithm for single-source shortest paths in graphs that may have negatively weighted edges but no negative cycles can be sped up by a technique of Yen in which the graph is partitioned into two directed acyclic subgraphs and edge relaxations alternate between these two subgraphs. We show that choosing this partition randomly gains an additional factor of 2/3 in running time.