Has anyone read the new paper from April 2025 that claims a faster algorithm for the directed, non-negative weights single-source shortest path problem?

They claim a deterministic time complexity of $$$O(m \log^{2/3} n)$$$, which would beat the long-assumed $$$\Omega(n \log n)$$$ lower bound on sparse graphs.

Link: https://arxiv.org/abs/2504.17033

Is this legit, and has anyone attempted to implement this yet?

I am looking for a reference implementation in any language (preferably in C++, Java, Rust, or Python).

I would be interested in any links, repositories, or performance comparisons that are available, as I was unable to find any online.

I am also curious about any thoughts on this paper from the Codeforces community.

Thanks!

:)

UPD: I think the paper is legit since it was accepted into STOC 2025 and won the best paper award.

It was accepted here and won the best paper award in the schedule here.

Hi, Codeforces!

From Friday, April 28th, to Sunday, April 30th, DMOJ will be hosting the second Max's Anger Contest. Participants will be given a 2-hour window to complete 5 problems in each contest. Note that this contest is NOT rated. To participate, you must register an account on DMOJ. The difficulty of the problems is approximately Div. 3 level.

Additionally, the top 5 competitors and a random non-zero score participant in the contest will receive Discord Nitro prizes with more details at https://dmoj.ca/post/256-maxs-anger-contest-series-2.

More information can be found at https://dmoj.ca/contest/macs2 for the contest. We hope you enjoy the problems and have fun!

Hope to see you soon!

Hi, Codeforces!

From Friday, December 30th, to Sunday, January 1st, DMOJ will be hosting the first Max's Anger Contest. Participants will be given a 2-hour window to complete 5 problems in each contest. Note that this contest is NOT rated. To participate, you must register an account on DMOJ. The difficulty of the problems is approximately Div. 3 level.

Additionally, the top 5 competitors and a random non-zero score participant in the contest will receive Discord Nitro prizes with more details at https://dmoj.ca/post/250-maxs-anger-contest-series-1.

More information can be found at https://dmoj.ca/contest/macs1 for the contest. We hope you enjoy the problems and have fun!

Hope to see you soon!

Hi, Codeforces!

From Friday, May 20th to Sunday, May 22nd, DMOJ will be hosting the fifth SAC Code Challenge and the third SAC Code Challenge Junior. Participants will be given a 2-hour window to complete 5 problems in each contest. Note that these contests are NOT rated. To participate, you must register an account on DMOJ. The difficulty of the junior problems is approximately Div. 4 level; the difficulty of the main problems is approximately Div. 3 level.

Additionally, the top 5 competitors in the main contest will receive 1 month of Discord Nitro with more details at https://dmoj.ca/post/232-sac-code-challenge-5-2022.

More information can be found at https://dmoj.ca/contest/sac22cc5j for the junior contest and https://dmoj.ca/contest/sac22cc5 for the main contest. We hope you enjoy the problems and have fun!

Hope to see you soon!

Hi, Codeforces!

From Friday, March 11th to Sunday, March 13th, DMOJ will be hosting the fourth SAC Code Challenge and the second SAC Code Challenge Junior. Participants will be given a 2-hour window to complete 5 problems in each contest. Note that these contests are NOT rated. To participate, you must register an account on DMOJ. The difficulty of the junior problems is approximately Div. 4 level; the difficulty of the main problems is approximately Div. 3 level.

Additionally, the top 5 competitors in the main contest will receive 1 month of Discord Nitro with more details at https://dmoj.ca/post/225-sac-code-challenge-4-2022.

More information can be found at https://dmoj.ca/contest/sac22cc4j for the junior contest and https://dmoj.ca/contest/sac22cc4 for the main contest. We hope you enjoy the problems and have fun!

Hope to see you soon!

Hi, Codeforces!

From Friday, February 11th to Sunday, February 13th, DMOJ will be hosting the third SAC Code Challenge and the first SAC Code Challenge Junior. Participants will be given a 2-hour window to complete 5 problems in each contest. Note that these contests are NOT rated. To participate, you must register an account on DMOJ. The difficulty of the junior problems is approximately Div. 4 level; the difficulty of the normal problems is approximately Div. 3 level.

More information can be found at https://dmoj.ca/contest/sac22cc3j for the junior contest and https://dmoj.ca/contest/sac22cc3 for the normal contest. We hope you enjoy the problems and have fun!

Hope to see you soon!

Hi, Codeforces!

From Friday, December 17th to Sunday, December 20th, DMOJ will be hosting the second SAC Code Challenge. Participants will be given a 2-hour window to complete 5 problems themed around Christmas. Note that this contest is NOT rated. To participate, you must register an account on DMOJ. The difficulty of the problems are approximately Div. 3 level.

More information can be found at https://dmoj.ca/contest/sac22cc2. We hope you enjoy the problems and have fun!

Hope to see you soon!