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

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

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

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

, каждой дуге (ребру)

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

этого графа сопоставлен неотрицательный вес

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

. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин
$Алгоритм Флойда нахождения кратчайших путей между парами вершин$
любого пути от вершины
$Алгоритм Флойда нахождения кратчайших путей между парами вершин$
в вершину
$Алгоритм Флойда нахождения кратчайших путей между парами вершин$
, длина которого минимальна среди всех возможных путей от
$Алгоритм Флойда нахождения кратчайших путей между парами вершин$
к
$Алгоритм Флойда нахождения кратчайших путей между парами вершин$
.

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

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

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

Главная сайта