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

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

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

, ,

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

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

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

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

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

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

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

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

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

. (2.1)

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

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

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

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

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

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

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

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

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

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

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

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