Комбинаторные алгоритмы для программистов

         

Алгоритм Флойда нахождения кратчайших путей между парами вершин


Предположим, что мы имеем помеченный орграф, который содержит время полета по маршрутам, связывающим определенные города, и~мы хотим построить таблицу, где приводилось бы минимальное время перелета из одного (произвольного) города в любой другой. В этом случае мы сталкиваемся с общей задачей нахождения кратчайших путей, то есть нахождения кратчайших путей между всеми парами вершин орграфа.

Формулировка задачи.Есть ориентированный граф

, каждой дуге (ребру)
этого графа сопоставлен неотрицательный вес
. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин
любого пути от вершины
в вершину
, длина которого минимальна среди всех возможных путей от
к
.

Можно решать эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но мы для решения поставленной задачи воспользуемся алгоритмом, предложенным Флойдом (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)



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