Исследование и реализация параллельного алгоритма поиска кратчайших путей в графе

Процесс работы алгоритма \delta на k-ом этапе можно представить в виде итераций [2]:
r_j^k= {█(r_j^(k-1),если r_j^(k-1)≤r_i^k+a_ij@r_i^k+a_ij,если r_j^(k-1)>r_i^k+a_ij ) ┤,где j=1,…,n,j≠i,a_ij≠0
∀i∈(1,…,n):r_i^k=min⁡(r_i^(k-1) ) p_i= false
Подобным образом, посредством разбиения на подзадачи можно воспользоваться алгоритмом Флойда-Уоршала и распараллелить процесс поиска кратчайших путей.
Алгоритм Флойда-Уоршалла - это алгоритм для вычисления кратчайшего пути между всеми парами вершин во взвешенном графе. Он особенно полезен, когда граф плотный, то есть когда количество ребер велико по отношению к количеству узлов.
Сначала все пары узлов инициализируются, устанавливая каждый узел на себя, а остальные - на бесконечность:
dist[i][j] = graph[i][j] для i,j=1,2,...,n
dist[i][i] = 0 для i=1,2,...,n
Далее применяется алгоритм:
Для каждого узла k от 1 до n проверяется расстояние между каждой парой узлов (i, j) и при необходимости обновляется:
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]) for i,j=1,2,...,n
В работах [3,4] рассматривается процесс распараллеливания вычислений с использованием данного алгоритма.
Как отмечают в [5] еще один алгоритм поиска кратчайших путей - алгоритм Джонсона используется для поиска кратчайших путей между всеми парами взвешенного направленного графа. Для разреженных графов он более эффективен, чем другие алгоритмы, такие как умножение матриц или алгоритм Флойда-Уоршалла. Алгоритм либо возвращает матрицу, содержащую веса кратчайших путей для всех пар вершин, либо сообщает о наличии отрицательного цикла в графе. Для этого алгоритм Джонсона использует алгоритм Беллмана-Форда для поиска отрицательных циклов и алгоритм Дейкстры для поиска кратчайших путей между вершинами [5].
Для реализации параллельного алгоритма поиска кратчайших путей в графе можно использовать различные подходы. Одним из наиболее известных является алгоритм Беллмана-Форда, основанный на принципе динамического программирования. В нем стоимость кратчайших путей обновляется шаг за шагом в ходе итераций до тех пор, пока не будут найдены все кратчайшие пути.
Алгоритм Беллмана-Форда может быть реализован параллельно несколькими способами, в зависимости от имеющегося оборудования и языка программирования, но реализация сводится к следующему:
1. Инициализация:
a. Инициализируем значения расстояния до всех узлов бесконечностью (кроме начального узла, у которого 0).
b. Создаем приоритетную очередь для узлов, подлежащих обработке, отсортированную по текущим значениям расстояния.
2. Повторяем следующий шаг до тех пор, пока не будет произведено больше никаких изменений:
a. Разделим узлы на несколько подмножеств, которые можно обрабатывать независимо друг от друга.
b. Для каждого подмножества узлов:
i. Обновим значения расстояний для соседних узлов, если был найден более короткий путь.
ii. Добавим узлы, значения расстояний которых были обновлены, в очередь приоритетов.
3. вернем значения расстояния до всех узлов
Ключом к параллельной реализации является организация шагов 2a и 2b таким образом, чтобы они могли выполняться одновременно различными процессами или потоками
1. Параллелизм на основе задач: разделите узлы на равные подмножества и назначьте подзадачу каждому процессу или потоку. Затем каждый процесс или поток выполняет шаг 2b независимо и параллельно.
2. параллелизм на основе потоков: создайте группу потоков, которые вместе обращаются к очереди приоритетов. Каждый поток берет узел из очереди, обновляет своих соседей и добавляет обновленные узлы в очередь по мере необходимости. Эта параллельная реализация может быть реализована с помощью механизмов синхронизации, таких как мьютекс или атомарные операции.
3. Параллелизм на основе процессов: разделите узлы на различные процессы и используйте такую технику, как интерфейс передачи сообщений (MPI), для координации взаимодействия между процессами. Затем каждый процесс выполняет шаг 2b независимо и параллельно.

Следующий рассматриваемый параллельный алгоритм Джонсона распределяет вычисления между несколькими потоками, при этом каждый поток выполняет последовательную версию алгоритма Дейкстры для заданного набора узлов. При изменении весов графа распределение ребер между потоками корректируется соответствующим образом [6].
Следует отметить, что выборе алгоритмы кратчайшего пути большую роль играет его специфика применения. Так, время вычисления алгоритма Дейкстры может быть непрактичным для больших графов из-за временной сложности O(V|2), где V - количество узлов в графе. Также алгоритм Дейкстры не может работать с отрицательными значениями ребер графа, что накладывает ограничения в его применении.
Из анализа источников можем систематизировать параметры распараллеливания алгоритмов поиска кратчайших путей и свести в таблицу их положительные и отрицательные качества для применения: