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

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

Громов Р.С. (НИУ ВШЭ, Москва, Россия)
Нестеров Р.А. (НИУ ВШЭ, Москва, Россия)

Аннотация

В статье исследуются критерии эффективности новейшего алгоритма для решения задачи поиска кратчайших путей на графе из заданной вершины – BM-SSP. Алгоритм был опубликован в 2025 году и, как утверждают его создатели, асимптотически превосходит детерминированный алгоритм Дейкстры. Однако в публикации, посвященной этому алгоритму, был дан только теоретический асимптотический анализ времени выполнения, и не было приведено ни одного бенчмарка, который доказал бы его практическую эффективность. Это исследование должно выявить и обосновать условия, при которых алгоритм BM-SSP демонстрирует превосходящую эффективность (с точки зрения времени выполнения и потребления ресурсов) по сравнению с классическими алгоритмами поиска кратчайших путей на графах различной структуры. Эти гипотезы должны быть подтверждены или опровергнуты результатами бенчмарков, которые будут проводиться на тестовой инфраструктуре с использованием разработанного фреймворка нагрузки для тестирования различных графиков.

Ключевые слова

графы; кратчайшие пути; поиск кратчайших путей из множества стартовых вершин; алгоритм Дейкстры; анализ временной сложности.

Издание

Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 23-44.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(4)-17

Для цитирования

Громов Р.С., Нестеров Р.А. Об эффективности алгоритма поиска кратчайшего пути на графе из множества стартовых вершин. Труды Института системного программирования РАН, том 38, вып. 4, часть 2, 2026, стр. 23-44. DOI: 10.15514/ISPRAS-2026-38(4)-17.

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома