On the Efficiency of Bounded Multi-Source Shortest Path Algorithm

On the Efficiency of Bounded Multi-Source Shortest Path Algorithm

Gromov R.S. (NRU HSE, Moscow, Russia)
Nesterov R.A. (NRU HSE, Moscow, Russia)

Abstract

This paper explores the performance criteria of the newest algorithm for solving the problem of finding shortest paths on a graph from a given vertex – Bounded Multi-Source Shortest Path Algorithm
(BM-SSP). The algorithm was published in 2025 and, as its creators claim, it is asymptotically superior to Dijkstra’s deterministic algorithm. However, in the publication devoted to this algorithm, only a theoretical asymptotic analysis of the execution time was given, and not a single benchmark was provided that would prove its practical effectiveness. This study should identify and substantiate the conditions under which the BM-SSP algorithm demonstrates superior efficiency (in terms of execution time and resource consumption) over classical algorithms for finding shortest paths on graphs of various structures. These hypotheses should be proved or disproved by the results of benchmarks that will be conducted on the test infrastructure using a built-in load framework for testing various graphs.

Keywords

Graphs; Shortest paths; Bounded Multi-Source Shortest Path algorithm; Dijkstra algorithm; Time complexity analysis.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 4, part 2, 2026, pp. 23-44

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

DOI: 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, vol. 38, issue 4, part 2, 2026, pp. 23-44 DOI: 10.15514/ISPRAS-2026-38(4)-17.

Full text of the paper in pdf Back to the contents of the volume