The End of Dijkstra’s Algorithm? Breaking the Sorting Barrier for Shortest Paths скачать в хорошем качестве

The End of Dijkstra’s Algorithm? Breaking the Sorting Barrier for Shortest Paths

A technical talk on the BMSSP algorithm introduced by Duan, Mao, Mao, Shu and Yin (2025) in the paper “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths.” Paper: https://arxiv.org/pdf/2504.17033 Presented at Churchill College, University of Cambridge, on 11 March 2026. To access the slides (and appendices, which are not shown in the main talk): https://drive.google.com/drive/folder... Synopsis: The paper Breaking the Sorting Barrier for Directed Single-Source Shortest Paths recently attracted significant attention in the algorithms community. It presents the first deterministic algorithm that beats the classical 𝑂(𝑚 + 𝑛 log⁡ 𝑛) running time of Dijkstra’s algorithm for the Single-Source Shortest Path (SSSP) problem on sparse graphs. Does this new algorithm truly replace Dijkstra’s algorithm in practice? What does this breakthrough mean for us? This talk provides a high-level overview of the BMSSP algorithm, compares it with Dijkstra’s algorithm, and discusses broader questions about algorithmic breakthroughs and what it means for one algorithm to be “better” than another. Acknowledgements Dr. John Fawcett, for the opportunity and approval of the talk topic Mr. Jamie Syiek, for his valuable advice Churchill College Audio-visual Team, for recording the event