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