Цель работы: реализовать параллельные версии алгоритмов поиска кратчайших путей на графах, выявить их достоинства и недостатки.
Для достижения цели работы необходимо решить следующие задачи:
1) Рассмотреть основные понятие теории графов и алгоритмы решения классической задачи на графах.
2) Реализовать параллельные версии распространенных и востребованных алгоритмов на языке C++.
3) Выявить достоинства, каждой из реализаций алгоритмов.
Отчет состоит из введения, трех глав и заключения.
В первой главе представлены теоретические аспекты теории графов, основные алгоритмы для решения задач с графами.
Во второй главе описана реализация параллельных алгоритмов Флойда и Джонсона на языке C++, и тестирование их работы.