38 лет считалось, что для разреженных графов алгоритм Дейкстры почти упёрся в потолок.
Логика выглядела железно:
- Дейкстра упорядочивает вершины по расстоянию
- сортировка имеет нижнюю границу O(n log n)
- значит, кратчайшие пути быстрее искать нельзя
Но группа из 5 исследователей показала, что это ограничение можно обойти.
Идея в том, чтобы не просто «ускорить очередь с приоритетами», а смешать подход Дейкстры с динамическим программированием в стиле Беллмана-Форда. Алгоритм делит множество вершин, сжимает frontier и не тратит время на полную сортировку там, где она не нужна.
Результат:
O(m log^(2/3) n)
Это первое улучшение для направленных разреженных графов со времён Fibonacci heap в 1987 году.
Tsinghua, Stanford, Max Planck. 17 страниц, которые ломают старое интуитивное объяснение про «Дейкстру быстрее нельзя».
