Теория и практика параллельных вычислений
Последовательный алгоритм Флойда
Для поиска минимальных расстояний между всеми парами пунктов назначения Флойд предложил алгоритм, сложность которого имеет порядок n3. В общем виде данный алгоритм может быть представлен следующим образом:
Алгоритм 10.1. Общая схема алгоритма Флойда
// Алгоритм 10.1 // Последовательный алгоритм Флойда for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) A[i, j] = min(A[i, j], A[i, k] + A[k, j]);
(реализация операции выбора минимального значения min должна учитывать способ указания в матрице смежности несуществующих дуг графа). Как можно заметить, в ходе выполнения алгоритма матрица смежности A изменяется, после завершения вычислений в матрице A будет храниться требуемый результат – длины минимальных путей для каждой пары вершин исходного графа.
Дополнительная информация и доказательство правильности алгоритма Флойда могут быть получены, например, в работе [[26]].
