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

Задача поиска кратчайших путей между всеми парами вершин в графе (APSP) имеет применяется в планировании, коммуникациях, экономике и многих других сферах. На сегодняшний день существует ряд алгоритмов решения APSP задач, начиная с алгоритма Флойда-Уоршелла (Floyd-Warshall) и заканчивая более продвинутыми и быстрыми блочными алгоритмами (например, неоднородным блочным алгоритмом поиска кратчайших путей Heterogeneous Blocked All-Pairs Shortest Paths), предназначенными для максимально эффективного использования вычислительных средств и зависимостей между данными, участвующими в вычислениях. В статье предлагается новый блочный алгоритм BSPCG поиска кратчайших путей в кластеризованных графах в однопоточном и многопоточном вариантах, который использует информацию о кластеризации для сокращения объема вычислений посредством поиска кратчайших путей, проходящих через граничные вершины кластеров. В статье проведена серия вычислительных экспериментов над стандартным блочным алгоритмом BFW и новым алгоритмом BSPCG с целью доказательства эффективности поиска кратчайших путей в случае использования граничных вершин кластеров. Эксперименты выполнялись с использованием графов размером 4800 и 9600 вершин с различными кластерными конфигурациями. Эксперименты проведены на компьютере с двумя процессорами Intel Xeon E5-2620v4 (каждый процессор включает 8 физических ядер и 16 аппаратных потоков, а также кэш L3 объемом 20 МБ). Во всех проведенных экспериментах новый алгоритм BSPCG превзошел стандартный алгоритм BFW в несколько раз. В однопоточных сценариях BSPCG продемонстрировал ускорение по сравнению с BFW до 4.6 раз на графах с 4800 вершинами и до 2.7 раз на графах с 9600 вершинами. В многопоточных сценариях BSPCG также продемонстрировал ускорение до 4 раз на графах с 4800 вершинами и до 2,7 раз на графах с 9600 вершинами. Предложенный в статье алгоритм может быть использован в сценариях, где информация о кластеризации остается неизменной или изменяется незначительно и может быть повторно использована для множественных нахождений всех кратчайших путей в графе.

1. Schrijver A. On the history of the shortest path problem. Documenta Mathematica. 2012. Vol. 17, № 1. P. 155–167.

2. Anu P., (Kumar) M.G. Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel FloydWarshall and Parallel Dijkstra Algorithms. Journal of Computing in Civil Engineering. 2013. Vol. 27, № 3. P. 263–273.

3. Ridi L., Torrini J., Vicario E. Developing a Scheduler with Difference Matrices and the Floyd-Warshall Algorithm. IEEE Software. 2012. Vol. 29, № 1. P. 76–83.

4. E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik. 1959. Vol. 1, № 1. P. 269–271.

5. Floyd R.W. Algorithm 97: Shortest Path. Communications of the ACM. 1962. Vol. 5, № 6. P. 345-.

6. Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing. Proceedings VIII International conference “Big data and advanced analytics”, Minsk: Bestprint, 2022. P. 56-66.

7. Prihozhy A., Karasik O. Heterogenious blocked all-pairs shortest paths algorithm. System analysis and Applied Information Science. 2017. № 3. P. 68–75.

8. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA). 2003. Vol. 8. P. 857–874.

9. Singh A., Mishra P.K. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm. International Journal of Computer Applications. 2014. Vol. 107, № 16. P. 23–27.

10. Karasik O., Prihozhy А. Requirements to methods of graph clustering at the aim of solving the shortest path problem. Proceedings X International conference “Big data and advanced analytics”, Minsk: BSUIR, 2024. P. 272–279.

11. Prihozhy A., Karasik O. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. System analysis and applied information science. BNTU, 2023. № 4. P. 4–13.

12. Prihozhy А., Karasik O. Blocked algorithm of shortest paths search in sparse graphs partitioned into unequally sized clusters. Proceedings X International conference “Big data and advanced analytics”, Minsk: BSUIR, 2024. P. 262–271.

13. Karasik O., Prihozhy A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System analysis and applied information science. BNTU, 2022. № 3. P. 57–65.

14. Karasik O., Prihozhy А. Parallel blocked all-pair shortest path algorithm: block size effect on cache operation in multicore system. Proceedings VIII International conference “Big data and advanced analytics”, Minsk: Bestprint, 2022. P. 28–38.

15. Prihozhy A., Karasik O. Influence of shortest path algorithms on energy consumption of multi-core processors. System analysis and applied information science. BNTU, 2023. № 2. P. 4–12.

16. Karasik O., Prihozhy A. Profiling of energy consumption by algorithms of shortest paths search in large dense graphs. Proceedings IX International conference “Big data and advanced analytics”, Minsk: BSUIR, 2023. P. 44–50.

17. Karasik O., Prihozhy A. Streaming block-parallel algorithm for finding shortest paths on a graph. Minsk: BSUIR 2018. № 2. P. 77–84.