Проанализируем алгоритм Флойда с точки зрения возможности распараллеливания и зависимости по данным. Алгоритм перебирает все узлы исходного графа и для каждого  ищет оптимальные пути, проходящие через этот узел. Таким образом, мы имеем две возможности для распараллеливания: перебор вершин и поиск оптимальных путей через текущий узел. Очевидно, что перебор вершин распараллелить нельзя, т.к. каждая следующая итерация алгоритма зависит по данным от предыдущей. Поиск оптимальных путей, распараллелить можно, т. к. все его итерации независимы. Таким образом мы можем разбить задачу на (N-1)^2 процессоров. При такой схеме распараллеливания каждый процессор, если число процессоров совпадает с числом вершин графа, получит текущую строку матрицы и один элемент из текущего столбца.

Зелёный - ведущий элемент

Красный - Поток №1

Синий - Поток №2

Красный+Синий - Общая память