Главная Обратная связь

Дисциплины:






Теоретическое описание метода Флойда



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

Пусть — нагруженный граф (орграф), содержащий вершин, для которого задана матрица весов ребер (дуг):

, ,

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

Дуги, имеющие отрицательные весы , можно рассматривать как приносящие некоторый доход при их прохождении. Если (положитель­ный вес), то прохождение по этой дуге связано с затратами.

Обозначим — множество первых вершин графа ( ). Длину кратчайшего пути из вершины в вершину , содержащего в качестве промежуточных только вершины из множества , обозначим . Если между вершинами и не существует ни одного указанного пути, то будем считать, что .

Пусть известны:

1) кратчайший путь из вершины в вершину , который в качестве промежуточных содержит только вершины из множества ; вершины ;

2) кратчайший путь из вершины в вершину , который в качестве промежуточных также содержит вершины из множества ;

3) кратчайший путь из вершины в вершину , проходящий как и два предыдущих только через вершины множества .

Объединяя все три пути, получим путь , проходящий через вершину . Так как по условию исходный граф не может содержать циклов отрицательного веса, один из двух путей или должен быть более коротким (в крайнем случае, они могут быть равны). Более короткий из этих путей является условно кратчайшим путем из вершины в , в котором в качестве промежуточных используются только вершины из множества .

Таким образом, выполняется соотношение

. (2.1)

Очевидно, что величины определяют верхние границы для длин кратчайших путей.

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

Формальное описание алгоритма

1. Подготовительный шаг. Определить матрицу , положив величину каждого ее элемента , равной длине дуги, соединяющей вершину c верши­ной : .

2. Общий шаг ( -шаг, ).

По матрице определить матрицу , используя рекуррентное соотношение (2.1).

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

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



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

В начале выполнения алгоритма помечаем:

На -м шаге каждый раз при использовании соотношения (2.1) проверяется, какой из весов или меньше. Если меньше оказывается вторая из этих величин, то полагается . В противном случае , т.е. соответствующий элемент не меняется.

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





sdamzavas.net - 2017 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...