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.
hope it's not another april fools prank
Meanwhile this paper has existed for quite a while now and claims a quite surprising time complexity... but I don't think anyone in competitive programming has tried it yet. If you want just $$$\tilde{\mathcal{O}}(m\sqrt{n})$$$ then $$$\mathcal{O}(m\sqrt{n}\log W)$$$ for integral weights has existed for around 30 years (Goldberg, 1995) and should be not too terrible (who even sets $$$W$$$ too large in a shortest path problem?).
Massive? Do you know what else is massive?
Who needs ford-bellman when dijkstra exists
Negative weights kills Dijkstra
Be positive, man! Just make the weight positive!
Let $$$w_\text{new}(u,v)=w(u,v)-\min{w}$$$.
And we can prove that for all $$$u,v$$$，$$$w_\text{new}(u,v)$$$ is not Negative.
(There might be a few issues.)