ДО 4 БАЛЛОВ ЗА КОНСПЕКТ
Алгоритм Флойда определения кратчайших путей между всеми парами вершин данного графа
Если в графе р вершин, требуется отыскать кратчайших путей.
Произвольно перенумеруем вершины графа числами от 1 до р.
Обозначим через длину пути от вершины i до вершины j, кратчайшего из всех путей от i до j, промежуточные вершины которых имеют номера, не превосходящие k.
Числа находятся сразу - это длины путей без промежуточных вершин.
Числа – это длины кратчайших путей.
Опишем переход от чисел к числам
(рис. 8).
Разрешение вершине с номером быть промежуточной добавляет к известным путям от вершины i до вершины j еще один путь, проходящий через вершину с номером
. Он состоит из двух частей (рис. 8): пути от
вершины i до вершины
длины
и пути от вершины
до вершины j длины
. Тогда
. (4)
Если в графе р вершин, то требуется р раз вычислять величин
(
,
;
). При этом удобно использовать матрицы D 0, D 1, …, Dp размера
. В матрице Dk стоят числа
,
,
.
Количество вычислений можно сократить. При переходе от матрицы Dk к матрице Dk+ 1 не нужно пересчитывать строку и столбец с номером , они переносятся из матриц Dk. В самом деле
Подобным образом
Попросту говоря, если вершина с номером - промежуточная вершина некоторого пути, она не первая и не последняя вершина этого пути, поэтому длины путей, которые начинаются (заканчиваются) в вершине
не меняются, если вершине
разрешено быть промежуточной.
Пример. Определим длины кратчайших путей между всеми парами вершин графа, изображенного на рис. 9.
Перейдем от матрицы D 0 к матрице D 1. Первую строку и первый столбец матрицы D 1 переносим из матрицы D 0.
![]() | |||||
∞ | -3 | ||||
∞ | -1 | ∞ | |||
∞ | ∞ | ||||
∞ | -1 | ∞ | |||
Кроме того, . Это означает отсутствие пути из первой вершины в четвертую, что, в свою очередь, означает невозможность найти новые пути в четвертую вершину через первую вершину. Четвертый столбец матрицы D 1 переносится из матрицы D 0.
В матрице D 0 первом столбце и четвертой строке также стоит бесконечность, из четвертой вершины в вершину 1 пути нет, невозможно найти новые пути, выходящие из четвертой вершины с промежуточной вершиной 1. Строка 4 матрицы D 1 переписывается из матрицы D 0.
Осталось рассчитать элементы ,
,
,
,
,
.
;
;
;
;
;
.
Определим элементы матрицы D 2. Вторую строку и второй столбец матрицы D 2 переносим из матрицы D 1.
| |||||||||||||||||||||||||||||||||||||||
|
Находим длины ,
,
,
,
,
,
,
,
,
,
,
.
;
;
;
;
;
;
;
;
;
;
;
.
Матрицы D 3, D 4, D 5 строятся аналогично. Приведем их без дальнейших пояснений (стр. 274).
Построение деревьев кратчайших путей.
В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев.
Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D 5) и ориентируясь по диаграмме на рис. 9.
Деревья показаны на рис. 10.
Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы Dp по крайней мере одна длина сохраняется такой же, какой она была в матрице D 0 (длина кратчайшего пути из одной дуги). В нашем случае имеем:
Эти числа показаны в матрице жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.
Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.