Dijkstra is not optimal — proven by Codeforces legends

Revision en2, by MladenP, 2025-06-02 21:44:46

No, this is not clickbait (maybe). Researchers Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu and Longhui Yin recently published a paper showing their deterministic $$$O(m\log^{2/3} n)$$$ algorithm for the directed Single-Source Shortest Path problem on sparse directed graphs — breaking almost 70 years of Dijkstra's reign in this field. I have yet to read it (looking forward to it, hopefully I can understand it) — but this shows that the common misconception that all interesting algorithms have been discovered is very wrong.

Also, if the name Xiao Mao sounds familiar — it did to me as well. It's the real name of matthew99, former LGM and ICPC World Champion — not sure if that's him, but it would be cool. Also found a GM Jiayi Mao on CF — AbstractKangaroo. Again — I have no idea how common these names are, but it wouldn't surprise me if it's them :)

Tags dijkstra, matthew99

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MladenP 2025-06-02 21:44:46 10
en1 English MladenP 2025-06-02 21:15:37 1024 Initial revision (published)