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

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

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