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

ДО 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 ₀ (длина кратчайшего пути из одной дуги). В нашем случае имеем:

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

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