Алгоритмы поиска кратчайших путей на графах нашли свое применение в различных областях и сферах деятельности человека. Такие алгоритмы используются в картографических сервисах, при построении пути GPS-навигатора, для представления и анализа дорожной сети и во многих других областях.
При проектировании компьютерных сетей, телевизионных линий, трубопроводов и строительстве дорог необходимо минимизировать затраты на прокладку коммуникаций. Прежде всего, целесообразно выбрать минимальный по длине маршрут прокладки коммуникаций. Например, необходимо соединить телефонным или оптоволоконным кабелем несколько зданий, расстояния между которыми различны. Возникает задача определения маршрута прокладки кабеля минимальной длины, но при этом к каждому зданию. Для решения таких задач часто используют теорию графов.
В настоящее время существует большое число алгоритмов и подходов, которые решают данные задачи. Кроме того, в большинстве своем алгоритмы можно логически разделить на два класса - алгоритмы поиска кратчайшего расстояния от одной вершины до всех остальных и алгоритмы поиска кратчайших расстоянии между каждой парой вершин. Из первого класса самыми яркими представителями являются различные модификации алгоритмов Дейкстры и Беллмана-Форда. Для решения задач второго класса часто используются алгоритмы Флойда-Уоршелла и алгоритм Джонсона.
Наиболее распространённой библиотекой, использующейся для решения этих задач, является BGL (Boost Graph Library). Также для работы с графами используется библиотека LEDA. Однако эти библиотеки включают в себя только последовательные версии алгоритмов для решения задач на графах.
Актуальность:
С ростом многопроцессорных архитектур мы получили мощный инструмент для эффективного расчета искомых расстояний - мы получили возможность запускать эти алгоритмы на нескольких вычислительных ядрах. При этом в контексте с параллельными алгоритмами на графах встал вопрос об эффективном использовании ресурсов системы. Эта задача, однако, не имеет такого высокого разнообразия решений, как в случае однопоточного алгоритма. Существующие же решения довольно специфичны и не всегда работают эффективно на всех графовых структурах.
Объект работы: параллельный алгоритм нахождения кратчайших путей в графе.
Предмет исследования: сравнительный анализ параллельных реализаций алгоритмов нахождения кратчайшего пути на графе на языке программирования C++.
Цель работы: реализовать параллельные версии алгоритмов нахождения кратчайших путей на графе, выявить их достоинства и недостатки.
Для достижения цели работы необходимо решить следующие задачи:
1) Рассмотреть основные понятие теории графов и алгоритмы решения классической задачи на графах.
2) Реализовать параллельные версии распространенных и востребованных алгоритмов на языке C++.
3) Проверить работоспособность и корректность работы программ.
4) Выявить достоинства, каждой из реализаций алгоритмов.
Отчет состоит из введения, трех глав и заключения.
В первой главе представлены теоретические аспекты теории графов, основные алгоритмы для решения задач с графами.
Во второй главе описана реализация параллельных алгоритмов Флойда и Джонсона на языке C++, и тестирование их работы.
В третьей главе производится сравнительный анализ реализаций.
В ходе выполнения бакалаврской работы рассмотрены теоретические аспекты теории графов, алгоритмы решения классической задачи нахождение кратчайшего пути, достоинства и недостатки алгоритмов, а также реализации параллельных алгоритмов Беллмана-Форда и Джонсона на языке программирования C++.
Поиск кратчайшего пути - важная задача, возникающая в разных областях науки и техники: в экономике, робототехнике, в компьютерных играх и так далее. Исходя из того, что для решения всех четырех классических типов задач поиска кратчайших путей на графе, достаточно решить задачу 4 типа (нахождения кратчайшего пути от всех вершин ко всем вершинам), были реализованы параллельные версии классических алгоритмов для решения задач 4 типа.
В результате работы были пошагово реализованы параллельные алгоритмы Флойда, Джонсона на языке программирования C++ с применением технологии параллельного программирования OpenMP.
Вычислительные эксперименты, состоящие в сравнении времени работы данных параллельных алгоритмов, с последовательными аналогами, показали, что параллельный алгоритм Флойда позволяет получить значительно лучшее ускорение, чем параллельный алгоритм Джонсона.
Алгоритм Флойда так же показал, что с возрастанием количества вершин графа наибольшее ускорение получается при использовании наибольшего количества потоков. И напротив, для небольших графов выгоднее использовать меньшее количество потоков.
Однако в рамках рассмотренной задачи с графом карты дорог, алгоритм Джонсона значительно выигрывает, за счет того, что в основе лежит алгоритм Дейкстры эффективно работающий на разряженных графах.
