Алгоритм Флойда нахождения кратчайших путей между парами вершин
Предположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и~мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождения кратчайших путей, то есть нахождения кратчайших путей между всеми парами вершин орграфа.
Формулировка задачи.Есть ориентированный граф
Можно решать эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но мы для решения поставленной задачи воспользуемся алгоритмом, предложенным Флойдом (R.W. Floyd). Пусть все вершины орграфа последовательно пронумерованы от 1 до
в вершину
Над матрицей
Вычисление на
Верхний индекс
после
Для вычисления
изменяется. Рассмотрим орграф:
Рис. 16.1. Помеченный орграф
Матрица A(3 * 3) на нулевой итерации (k = 0)
Матрица A(3 * 3) после первой итерации (k = 1)
Матрица A(3 * 3) после второй итерации (k = 2)
Матрица A(3 * 3) после третьей итерации (k = 3)
