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

S_p = n³/(n³/p) = p,

E_p = n³/(p(n³⁄p)) = 1.

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

T_p(comm) = n log₂ p (α + ωn/β)

, где α– латентность сети передачи данных, β – пропускная способность сети, а ω есть размер элемента матрицы в байтах. С учетом полученных соотношений общее время выполнения параллельного алгоритма Флойда может быть определено следующим образом:

T_p = n²(n/p) τ + n log₂ p (α + ωn/β),

где τ есть время выполнения операции выбора минимального значения.