Об эффективности алгоритма поиска кратчайших путей на графе из множества стартовых вершин
https://doi.org/10.15514/ISPRAS-2026-38(4)-17
Аннотация
В статье исследуются критерии эффективности новейшего алгоритма для решения задачи поиска кратчайших путей на графе из заданной вершины – BM-SSP. Алгоритм был опубликован в 2025 году и, как утверждают его создатели, асимптотически превосходит детерминированный алгоритм Дейкстры. Однако в публикации, посвященной этому алгоритму, был дан только теоретический асимптотический анализ времени выполнения, и не было приведено ни одного бенчмарка, который доказал бы его практическую эффективность. Это исследование должно выявить и обосновать условия, при которых алгоритм BM-SSP демонстрирует превосходящую эффективность (с точки зрения времени выполнения и потребления ресурсов) по сравнению с классическими алгоритмами поиска кратчайших путей на графах различной структуры. Эти гипотезы должны быть подтверждены или опровергнуты результатами бенчмарков, которые будут проводиться на тестовой инфраструктуре с использованием разработанного фреймворка нагрузки для тестирования различных графиков.
Ключевые слова
графы,
кратчайшие пути,
поиск кратчайших путей из множества стартовых вершин,
алгоритм Дейкстры,
анализ временной сложности
При поддержке: Исследование осуществлено в рамках Программы фундаментальных исследований НИУ ВШЭ (HSE-BR-2025-024).
Об авторах
Роман Сергеевич ГРОМОВ
Национальный исследовательский университет “Высшая школа экономики”
Россия
Россия
Студент 4-го курса бакалаврской программы «Программная инженерия» (НИУ Высшая школа экономики, Москва). Его исследовательские интересы лежат в области разработки надежных высоконагруженных распределенных информационных систем, систем управления базами данных, а также в области сетевых протоколов передачи данных.
Роман Александрович НЕСТЕРОВ
Национальный исследовательский университет “Высшая школа экономики”
Россия
Россия
Доцент департамента программной инженерии факультета компьютерных наук, заведующий научно-учебной лабораторией процессно-ориентированных информационных систем НИУ Высшая школа экономики, кандидат компьютерных наук НИУ Высшая школа экономики с 2022 г. Его научные интересы включают подходы к моделированию и анализу поведения сложно организованных информационных систем, с помощью сетей Петри, теорию категорий и общую теорию параллелизма.
Список литературы
1. Bast H., Delling D., Goldberg A., Müller-Hannemann Ma., Pajor T., Sanders P., Wagner D., Werneck R., Route planning in transportation networks. In Algorithm Engineering: Selected Results and Surveys, Springer, 2016, 19-80. DOI: 10.1007/978-3-319-49487-6.
2. Retvari G., Tapolcai J., Enyedi G., Csaszar, A. IP fast reroute: Loop-free alternates revisited. IEEE INFOCOM 2011, pp. 294–298. DOI: 10.1109/INFCOM.2011.5935135.
3. Cowen L., Ideker T., Raphael B. J., Sharan, R. Network propagation: a universal amplifier of genetic associations. Nature Reviews Genetics, 2017, vol. 18(9), pp. 551–562. DOI: 10.1038/nrg.2017.38.
4. Angles R., Gutierrez C. Survey of graph database models. ACM Computing Surveys (CSUR), 2008, vol. 40, issue 1, pp. 1-39. DOI:10.1145/1322432.1322433.
5. Duan R., Mao J., Mao X., Shu X., Yin L. Breaking the sorting barrier for directed single-source shortest paths. Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, pp. 36-44. Also available at: https://arxiv.org/pdf/2504.17033, accessed 01.08.2026.
6. Makowski C., Guter W., Russell T., Saragih A., Castro L. BMSSPy: A Python Package and Empirical Comparison of Bounded Multi-Source Shortest Path Algorithm. MIT Center for Transportation & Logistics, 2025 Research Paper No. 2025/034. DOI: 10.2139/ssrn.5777186. Also available at: https://ssrn.com/abstract=577718, accessed 01.08.20266.
7. Castro L., Clementino T., de Freitas R. Implementation and Experimental Analysis of the Duan et al., 2025. Algorithm for Single-Source Shortest Paths. DOI: 10.48550/arXiv.2511.03007.
8. Moore E.F. The shortest path through a maze. Proc. of the International Symposium on the Theory of Switching. Harvard University Press, 1959, pp. 285-292.
9. Bellman R., On a routing problem. Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, Apr. 1958. DOI: 10.1090/qam/102435.
10. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, Jun. 1962, vol. 5, no. 6, p. 345. DOI: 10.1145/367766.368168.
11. Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik, Dec. 1959, vol. 1, no. 1, pp. 269-271. DOI: 10.1007/BF01386390.
12. Fredman M.L., Tarjan R.E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, Jul. 1987, vol. 34, no. 3, pp. 596-615. DOI: 10.1145/28869.28874.
13. Ahuja R.K., Mehlhorn K., Orlin J.B., Tarjan R.E. Faster algorithms for the shortest path problem. Journal of the ACM, Apr. 1990, vol. 37, no. 2, pp. 213-223. DOI: 10.1145/77600.77605.
14. Liu et al. bmssp: Implementation of the Duan et al. BM-SSP algorithm. GitHub repository, 2024. Available at: https://github.com/lcs147/bmssp.
15. GraphOnline. GraphOnline: Online Graph Visualization and Analysis Tool. Available at: https://graphonline.top, accessed: 14.04.2026.
16. mrForza, Graphene. GitHub repository. Available at: https://github.com/mrForza/graphene, accessed: 15.04.2026.
Рецензия
Для цитирования:
ГРОМОВ Р.С., НЕСТЕРОВ Р.А. Об эффективности алгоритма поиска кратчайших путей на графе из множества стартовых вершин. Труды Института системного программирования РАН. 2026;38(4):23-44. https://doi.org/10.15514/ISPRAS-2026-38(4)-17
For citation:
GROMOV R.S., NESTEROV R.A. On the Efficiency of Bounded Multi-Source Shortest Path Algorithm. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2026;38(4):23-44. https://doi.org/10.15514/ISPRAS-2026-38(4)-17
Послать статью по эл. почте 