Повышение эффективности алгоритма Дейкстры с помощью технологий параллельных вычислений с библиотекой OpenMP

Аннотация

Аль-Саиди А.А.,Темкин И.О., Алтай В.И., Алмунтафеки А.Ф., Мохмедхуссин А.Н.

Дата поступления статьи: 12.06.2023

Целью исследования является повышение эффективности алгоритма Дейкстры за счет использования модели разделяемой памяти с библиотекой OpenMP и работы по принципу параллельного выполнения при реализации алгоритма. Использование алгоритма Дейкстры для поиска кратчайшего пути между двумя узлами в графе довольно распространено. Однако временная сложность алгоритма возрастает с увеличением размера графа, что приводит к увеличению времени выполнения, поэтому параллельное выполнение является хорошим вариантом для решения проблемы временной сложности. В этой исследовательской работе предлагается метод параллельных вычислений для повышения эффективности алгоритма Дейкстры для больших графов. метод включает в себя разделение массива путей в алгоритме Дейкстры на указанное количество процессоров для параллельного выполнения. Мы предоставляем реализацию распараллеленного алгоритма Дейкстры и получаем доступ к его производительности, используя фактические наборы данных и с разным количеством узлов. Наши результаты показывают, что распараллеленный алгоритм Дейкстры может значительно ускорить процесс по сравнению с последовательной версией алгоритма, одновременно сокращая время выполнения и постоянно повышая эффективность процессора, что делает его полезным выбором для поиска кратчайших путей в больших графах.

Ключевые слова: Алгоритм Дейкстры, граф, кратчайшие пути, параллельный вычислений, модель общей памяти, библиотека OpenMP

2.3.1 - Системный анализ, управление и обработка информации

.