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

Граф G – это упорядоченная пара G =(V, E), для которой набор вершин задается множеством V, а список дуг графа определяется множеством E. Дугам графа могут приписываться некоторые числовые характеристики – веса (взвешенный граф).

Элемент матрицы характеризует вес ребра, входящего в вершину. На главной диагонали матрицы стоят нули. Для обозначения отсутствия ребра между вершинами при вычислениях используется какое-либо отрицательное число. Использование матрицы смежности позволяет применять при реализации вычислительных процедур анализа графов матричные алгоритмы обработки данных.

В данной работе рассматривается задача поиска кратчайших путей между каждой парой вершин графа. Исходной информацией для задачи является взвешенный ориентированный граф, в котором каждому ребру графа приписан неотрицательный вес. Одним из методов, решающих задачу поиска кратчайших путей, является алгоритм Флойда, разработанный в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

В данной лабораторной работе необходимо:

1) Реализовать последовательную версию алгоритма Флойда.

2) Реализовать параллельную версию алгоритма Флойда с помощью библиотеки MPI.

3) Оценить эффективность параллельной схемы и привести результаты вычислительных экспериментов.