На днях прошла новость: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Классический Дейкстра устроен так: мы храним вершины в приоритетной очереди и итеративно выбираем ближайшую, проверяя рёбра и обновляя расстояния, если путь через текущее ребро короче. Узкое место тут как раз в необходимости постоянно поддерживать упорядоченность большой очереди вершин.

Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.

Но вот, что сделали авторы тут:

1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.

Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.

Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:

– В графовых нейросетях на основе расстояний между вершинами часто вычисляются самые важные фичи.
– Для всяких ML-алгоритмов для логистики просто незаменимо.
– И даже в RL есть применение. Например, при обучении роботов среда может быть представлена как граф состояний, в котором оптимальная политика – это кратчайший путь.

Отсюда: Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру

Здесь основная идея — это гибрид из алгоритма Дейкстры и алгоритма Беллмана-Форда.

Но если я все правильно понял, то в общем случае
* Новый алгоритм: O(m log²/³ n)
* Алгоритм Дейкстры: O(m + n log n)

1. Разреженные графы (Sparse Graphs): В таких графах количество рёбер m сопоставимо с количеством вершин n, то есть m ≈ n.
* Новый алгоритм: O(n log²/³ n)
* Алгоритм Дейкстры: O(n + n log n) = O(n log n)
* Вывод: В этом случае n log²/³ n растёт медленнее, чем n log n, поэтому новый алгоритм быстрее. Именно это и является его главным достижением, как указано в документе.

2. Плотные графы (Dense Graphs): В таких графах количество рёбер m близко к максимально возможному, то есть m приближается к n².
* Новый алгоритм: O(n² log²/³ n)
* Алгоритм Дейкстры: O(n² + n log n) = O(n²)
* Вывод: В этом случае n² растёт медленнее, чем n² log²/³ n. Поэтому на плотных графах алгоритм Дейкстры будет быстрее.

Получается что новый алгоритм эффективнее алгоритма Дейкстры на разреженных графах. Однако для плотных графов классический алгоритм Дейкстры остаётся более быстрым решением.

Так?