На этом шаге мы приведем анализ эффективности алгоритма Флойда.
Выполним анализ эффективности параллельного алгоритма Флойда, обеспечивающего поиск всех кратчайших путей.
Общая трудоемкость последовательного алгоритма является равной n3. Для параллельного алгоритма на отдельной итерации каждый процессор выполняет обновление элементов матрицы А. Всего в подзадачах n2/p таких элементов, число итераций алгоритма равно n, таким образом, показатели ускорения и эффективности параллельного алгоритма Флойда имеют вид:
Для уточнения полученных соотношений введем в полученные выражения время выполнения базовой операции выбора минимального значения и учтем затраты на выполнение операций передачи данных между процессорами.
Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы А всем
процессорам вычислительной системы. Выполнение такой операции может быть выполнено за 
шагов. С учетом количества итераций алгоритма Флойда общая длительность выполнения коммуникационных операций может быть определена при
помощи следующего выражения:
где, как и ранее, альфа - латентность сети передачи данных, бета - пропускная способность сети, а w есть размер элемента матрицы в байтах.
С учетом полученных соотношений общее время выполнения параллельного алгоритма Флойда может быть определено следующим образом:
где 
есть время выполнения операции выбора минимального значения.
На следующем шаге мы рассмотрим результаты вычислительных экспериментов.
