ДО 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 (длина кратчайшего пути из одной дуги). В нашем случае имеем:
Эти числа показаны в матрице 
жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.
Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.
