Построение деревьев кратчайших путей

ДО 4 БАЛЛОВ ЗА КОНСПЕКТ

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

Если в графе р вершин, требуется отыскать кратчайших путей.

Произвольно перенумеруем вершины графа числами от 1 до р.

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

Числа находятся сразу - это длины путей без промежуточных вершин.

Числа – это длины кратчайших путей.

Опишем переход от чисел к числам (рис. 8).

Разрешение вершине с номером быть промежуточной добавляет к известным путям от вершины i до вершины j еще один путь, проходящий через вершину с номером . Он состоит из двух частей (рис. 8): пути от

вершины i до вершины длины и пути от вершины до вершины j длины . Тогда

. (4)

Если в графе р вершин, то требуется р раз вычислять величин ( , ; ). При этом удобно использовать матрицы D₀, D₁,…, D_p размера . В матрице D_k стоят числа , , .

Количество вычислений можно сократить. При переходе от матрицы D_k к матрице D_k+1 не нужно пересчитывать строку и столбец с номером , они переносятся из матриц D_k. В самом деле

Подобным образом

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

Пример. Определим длины кратчайших путей между всеми парами вершин графа, изображенного на рис. 9.

Перейдем от матрицы D₀ к матрице D₁. Первую строку и первый столбец матрицы D₁ переносим из матрицы D₀.

				∞	-3
			∞	-1	∞
		∞			∞
	∞		-1		∞

Кроме того, _. Это означает отсутствие пути из первой вершины в четвертую, что, в свою очередь, означает невозможность найти новые пути в четвертую вершину через первую вершину. Четвертый столбец матрицы D₁ переносится из матрицы D_{0 .}

В матрице D₀ первом столбце и четвертой строке также стоит бесконечность, из четвертой вершины в вершину 1 пути нет, невозможно найти новые пути, выходящие из четвертой вершины с промежуточной вершиной 1. Строка 4 матрицы D₁ переписывается из матрицы D₀.

Осталось рассчитать элементы , , , , , .

_;

_;

_;

_{; ;}

_.

Определим элементы матрицы D₂. Вторую строку и второй столбец матрицы D₂ переносим из матрицы D₁.

	∞ -3 -1 ∞ -1 ∞
		-3 -1 -1

Находим длины , , , , , , , , , , , .

_;

_;

_;

_{; ;}

_{; ;}

_{; ;}

_{; ; .}

Матрицы D_3, D_4, D₅ строятся аналогично. Приведем их без дальнейших пояснений (стр. 274).

Построение деревьев кратчайших путей.

В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев.

Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D₅) и ориентируясь по диаграмме на рис. 9.

Деревья показаны на рис. 10.

Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы D_p по крайней мере одна длина сохраняется такой же, какой она была в матрице D₀ (длина кратчайшего пути из одной дуги). В нашем случае имеем:

Эти числа показаны в матрице жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.

Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.