Теория и практика параллельных вычислений

       

Последовательный алгоритм Флойда


Для поиска минимальных расстояний между всеми парами пунктов назначения Флойд предложил алгоритм, сложность которого имеет порядок 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]].



Содержание раздела