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

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

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

Общий анализ сложности дает идеальные показатели эффективности параллельных вычислений.

Коммуникационная операция, выполняемая на каждой итерации алгоритма Флойда, состоит в передаче одной из строк матрицы D всем процессорам вычислительной системы. Выполнение такой операции может быть выполнено за log₂ p шагов.

Общая длительность выполнения коммуникационных операций:

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

где α – латентность сети передачи данных, β – пропускная способность сети, w – размер элемента матрицы в байтах.

Общее время выполнения параллельного алгоритма Флойда:

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

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