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



             

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


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

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

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

Можно решать эту задачу, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве источника. Но мы для решения поставленной задачи воспользуемся алгоритмом, предложенным Флойдом (R.W. Floyd). Пусть все вершины орграфа последовательно пронумерованы от 1 до

n
. Алгоритм Флойда использует матрицу
A(n \times n)
, в которой находятся длины кратчайших путей:

A_{ij} = C_{ij}
, если
i \ne j
;

A_{ij} = 0
, если
i = j
;

A_{ij} = \infty
если отсутствует путь из вершины
i

в вершину

j
.

Над матрицей

A
выполняется
n
итераций. После
k
-й итерации
A_{ij}
содержит значение наименьшей длины пути из вершины
i
в вершину
j
, причем путь не проходит через вершины с номерами большими
k
.

Вычисление на

k
-ой итерации выполняется по формуле:
A_{ij}^k = \min (A_{ij}^{k - 1},A_{ik}^{k - 1},A_{kj}^{k - 1} )

Верхний индекс

k
обозначает значение матрицы
A

после

k
-ой итерации.

Для вычисления

A_{ij}^k
проводится сравнение величины
A_{ij}^{k -1}
(то есть стоимость пути от вершины
i
к вершине
j
без участия вершины
k
или другой вершины с более высоким номером) с величиной
A_{ik}^{k - 1} + A_{kj}^{k - 1}
(стоимость пути от вершины
i
к вершине
k
плюс стоимость пути от вершины
k
до вершины
j
). Если путь через вершину
k
дешевле, чем
A_{ij}^{k - 1}
, то величина
A_{ij}^k

изменяется. Рассмотрим орграф:

Помеченный орграф

Рис. 16.1.  Помеченный орграф

Матрица A(3 * 3) на нулевой итерации (k = 0)

 \left[ {\begin{array}{*{20}c} 0 & 8 & 5 \\ 3 & 0 & \infty \\ \infty & 2 & 0 \\ \end{array} } \right]

Матрица A(3 * 3) после первой итерации (k = 1)

 \left[ {\begin{array}{*{20}c} 0 & 8 & 5 \\ 3 & 0 & 8 \\ \infty & 2 & 0 \\ \end{array} } \right]

Матрица A(3 * 3) после второй итерации (k = 2)

 \left[ {\begin{array}{*{20}c} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array} } \right]

Матрица A(3 * 3) после третьей итерации (k = 3)

 \left[ {\begin{array}{*{20}c} 0 & 7 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array} } \right]




Содержание  Назад  Вперед