38 лет в Computer Science считалось, что алгоритм Дейкстры уже близок к пределу для разреженных графов.

Логика выглядела убедительно:
• Дейкстра упорядочивает вершины по расстоянию
• для сортировки существует нижняя граница O(n log n)
• значит, задачу кратчайших путей нельзя решить существенно быстрее

Оказалось, что это предположение было ошибочным.
Группа из 5 исследователей объединила очередь с приоритетом из алгоритма Дейкстры с динамическим программированием из алгоритма Беллмана—Форда. Затем они применили подход «разделяй и властвуй» к множествам вершин и сократили размер фронта поиска. Результат: O(m log^(2/3) n)

Это первое улучшение для направленных графов со времён появления Fibonacci Heap в 1987 году.
Участники работы: Тsinghua, Stanford и Max Planck Institute.
Всего 17 страниц.

👉 @PythonPortal