Hey everyone!

UC Berkeley's Satish Rao just published a paper improving the Bellman Ford algorithm. The bound that all of us know is $$$O(mn)$$$ but he published an $$$\tilde{O}(m\sqrt n)$$$ expected time algorithm (the ~ just means that there's some hidden logs in the complexity). This is a massive improvement over previous attempts to improve the $$$O(mn)$$$ algorithm, the last one being $$$\tilde{O}(mn^{\frac{4}{5}})$$$.

The paper is linked here: https://arxiv.org/pdf/2503.22613.

Although the bound looks very appealing I don't think it's practical for competitive algorithm as the ~ probably kills it. Regardless I think it's pretty cool since probably half the community here has heard of Bellman Ford.