Введение 14
Глава 1. Поиск кратчайших расстояний в графах 7
1.1 Основные понятия теории графов 7
1.2 Задачи поиска кратчайших путей на графах 9
1.3. Методы решения задачи поиска кратчайшего расстояния от
фиксированной вершины 10
1.3.1 Алгоритм Дейкстры 10
1.3.2. Алгоритм Беллмана-Форда 11
1.4. Методы решения задачи поиска кратчайших расстояний между каждой парой вершин 11
1.4.1 Алгоритм Флойда 12
1.4.2 Алгоритм Джонсона 14
Глава 2. Реализация и тестирование алгоритмов 17
2.1 Исходные данные 17
2.1.1 Формат данных 17
2.1.2 Обработка данных 18
2.2 Реализация алгоритма Флойда 19
2.2.1 Последовательный алгоритм 19
2.2.2 Параллельный алгоритм 22
2.3 Реализация алгоритма Джонсона 24
2.3.1 Последовательный алгоритм 24
2.3.2 Параллельный алгоритм 31
Глава 3. Сравнительный анализ реализаций 33
3.1 Тестовая инфраструктура 33
3.2 Практическое сравнение реализаций 34
3.2.1 Параллельный алгоритм Флойда 34
3.2.2 Параллельный алгоритм Джонсона 36
3.2.3 Сравнение алгоритмов между собой 37
Заключение 39
Список используемой литературы 40
Приложение А 42
Приложение B 44
Купить

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

Купить