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