Практическая работа № 7
Тема: «Поиск кратчайших путей между всеми вершинами графа
методом Флойда»
Теоретическое описание метода Флойда
Метод Флойда позволяет найти кратчайшие пути между всеми парами вершин графа.
Пусть 
— нагруженный граф (орграф), содержащий 
вершин, для которого задана матрица весов ребер (дуг):
, 
,
— вес дуги, соединяющей вершину 
с 
. На графе допускаются отрицательные весы дуг, однако не допускается наличие циклов отрицательного веса.
Дуги, имеющие отрицательные весы 
, можно рассматривать как приносящие некоторый доход при их прохождении. Если 
(положительный вес), то прохождение по этой дуге связано с затратами.
Обозначим 
— множество первых вершин графа (
). Длину кратчайшего пути из вершины в вершину , содержащего в качестве промежуточных только вершины из множества 
, обозначим 
. Если между вершинами и не существует ни одного указанного пути, то будем считать, что 
.
Пусть известны:
1) кратчайший путь из вершины в вершину , который в качестве промежуточных содержит только вершины из множества 
; вершины 
;
2) кратчайший путь из вершины 
в вершину , который в качестве промежуточных также содержит вершины из множества ;
3) кратчайший путь из вершины в вершину , проходящий как и два предыдущих только через вершины множества .
Объединяя все три пути, получим путь 
, проходящий через вершину . Так как по условию исходный граф не может содержать циклов отрицательного веса, один из двух путей или 
должен быть более коротким (в крайнем случае, они могут быть равны). Более короткий из этих путей является условно кратчайшим путем из вершины в , в котором в качестве промежуточных используются только вершины из множества .
Таким образом, выполняется соотношение
. (2.1)
Очевидно, что величины определяют верхние границы для длин кратчайших путей.
По мере расширения множества значения могут уменьшаться, пока не достигнут минимума. Уменьшение связано с выделением более коротких путей, ранее не учитываемых. Введем обозначение матрицы 
.
Формальное описание алгоритма
1. Подготовительный шаг. Определить матрицу 
, положив величину каждого ее элемента 
, равной длине дуги, соединяющей вершину c вершиной : 
.
2. Общий шаг (
-шаг, 
).
По матрице 
определить матрицу 
, используя рекуррентное соотношение (2.1).
Диагональные элементы пересчитывать не нужно, так как 
. Кроме того, при определении матрицы нет необходимости в пересчете элементов -ой строки и -го столбца, так как вершина не может служить в качестве промежуточной для путей, начинающихся или заканчивающихся в ней самой.
По окончании данного алгоритма (на шаге ) матрица 
определяет длины кратчайших путей, ведущих из вершины (
) в вершины (
, 
).
Для определения самых кратчайших путей наряду с матрицей весов , используются матрицы путей 
. Элемент 
указывает номер второй вершины на кратчайшем пути из в .
В начале выполнения алгоритма помечаем:
На -м шаге каждый раз при использовании соотношения (2.1) проверяется, какой из весов 
или 
меньше. Если меньше оказывается вторая из этих величин, то полагается 
. В противном случае 
, т. е. соответствующий элемент не меняется.
После окончания алгоритма кратчайшие пути могут быть получены непосредственно из заключительной матрицы 
.
1.2. Пример решения задачи методом Флойда
С помощью метода Флойда определим кратчайшие пути между вершинами нагруженного орграфа:
Решение.
1. Подготовительный шаг:
, 
.
2. Первый шаг (
). 
.
Определяем элементы матрицы 
. При этом элементы первой строки и первого столбца матрицы , а также диагональные элементы остаются без изменений:
, 
, 
.
Вычисляем остальные элементы матрицы :
,
,
,
,
,
.
Итак,
.
Определяем элементы матрицы 
.
Т. к. 
, то 
.
Т. к. 
, то 
.
Аналогично получаем
, 
, 
, 
.
Итак,
.
3. Второй шаг (
).
Определяем элементы матрицы 
. При этом элементы второй строки и второго столбца матрицы , а также диагональные элементы остаются без изменений:
, 
, 
, 
, 
,
, 
.
Вычисляем остальные элементы матрицы :
,
,
,
,
,
.
Итак,
, 
.
Определяем элементы матрицы 
:
, 
, 
, 
,
, 
, 
, 
,
, 
, 
, 
,
, 
, 
, 
.
Введение в рассмотрение дополнительной вершины 
не меняет минимальные пути между вершинами.
4. Третий шаг (
). 
.
Построив матрицы 
и 
, можно убедиться, что 
и 
. Т. е. введение в рассмотрение дополнительной вершины 
не меняет минимальные пути между вершинами.
5. Четвертый шаг (
). 
.
Вводится в рассмотрение вершина 
и находятся минимальные пути, проходящие через эту вершину.
Определяем элементы матрицы 
:
, 
, 
, 
,
, 
, 
,
,
,
,
,
,
.
Итак,
.
Определяем элементы матрицы 
:
, 
, 
, 
,
, 
, 
, 
,
, 
, 
, 
,
, 
, 
, 
.
Итак,
.
По матрице определяем искомые минимальные пути (см. таблицу 1).
Таблица 2.1. Минимальные пути
Начальная вершина | Конечная вершина | Путь | Длина пути |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. Индивидуальные задания
Исходными данными являются графы, представленные в табл. 2. Для всех вариантов задача состоит в отыскании кратчайшего маршрута между вершинами 
и 
.
Таблица 2. Исходные данные
|
|
Граф №1 | Граф №2 |
|
|
Граф №3 | Граф №4 |
|
|
Граф №5 | Граф №6 |
|
|
Граф №7 | Граф №8 |
|
|
Граф №9 | Граф №10 |
|
|
Граф №11 | Граф №12 |
|
|
Граф №13 | Граф №14 |
|
|
Граф №15 | Граф №16 |
|
|
Граф №17 | Граф №18 |
|
|
Граф №19 | Граф №20 |
|
|
Граф №21 | Граф №22 |
|
|
Граф №23 | Граф №24 |
|
|
Граф №25 | Граф №26 |
|
|
Граф №27 | Граф №28 |
|
|
Граф №29 | Граф №30 |
|
|
Граф №31 | Граф №32 |
|
|
Граф №33 | Граф №34 |
|
|
Граф №35 | Граф №36 |
Литература
1. Новиков математика для программистов. СПб.: Питер, 2002.
2. Конечные графы и сети. М.: Наука, 1973.
3. Теория графов и ее применение. М., 1962.
4. Теория графов. М.: Мир, 1973.
