BMSSP - Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Speaker(s)

Jan Kwieciński

Language of the talk

English

Date

Jan. 16, 2026, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

The single-source shortest path (SSSP) problem is a fundamental problem in graph algorithms. In 1959 E. W. Dijkstra proposed a O(m + n log n) algorithm. Since then, many algorithms have exploited various properties of different sub-classes of graphs - with no general solution. Until 2025 - when the BMSSP algorithm was published.

BMSSP is a deterministic O(m log^(2/3) n)-time algorithm for SSSP on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.

BMSSP was introduced in the ”Breaking the Sorting Barrier for Directed Single-Source Shortest Paths” paper by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin. The talk will also touch on the practical aspects of the algorithm.

---