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

Prelegent(ci)

Jan Kwieciński

Język referatu

angielski

Termin

16 stycznia 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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.

---