3. Кратчайшие пути между всеми парами вершин

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

В настоящем разделе мы опишем совершенно иной подход к задаче нахождения кратчайших путей между всеми парами вершин. Этот метод применим как к неотрицательным, так и к произвольным матрицам весов и время, необходимое для вычислений, пропорционально Бели этот метод применить к графам с неотрицательной матрицей весов, то он сэкономит почти 50% времени [11] по сравнению с -кратным применением алгоритма Дейкстры Метод был предложен первоначально Флойдом [13] и развит Мерчлэндом [27]. Он базируется на использовании последовательности из преобразований (итераций) начальной матрицы весов С При этом на итерации матрица представляет длины кратчайших путей между каждой парой вершин с тем ограничением, что путь между и (для любых содержит в качестве промежуточных только вершины из множества

3.1. Алгоритм Флойда (для произвольной матрицы весов)

Предположим, что в начальной матрице весов для всех если в графе отсутствует дуга

Присвоение начальных значений

Шаг 1. Положить

Итерация

Шаг 2.

Шаг 3. Для всех таких, что и для всех таких, что введем операцию

Проверка на окончание

Шаг Если то в графе существует цикл отрицательного веса, содержащий вершину и решения нет. Останов.

(б) Если все и то получено решение. Матрица дает длины всех кратчайших путей. Останов.

(в) Если все но к то вернуться к шагу 2.

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

Сами кратчайшие пути можно найти по их длинам с помощью рекурсивной процедуры, подобной той, которая выше определялась соотношением (8.2). С другой стороны, можно использовать технику, предложенную Ху [21], для записи информации о самих путях (наряду с информацией о длинах путей). Этот последний метод аналогичен использованному в разд. 2.2.1 и особенно полезен в тех случаях, когда требуется найти в графе цикл отрицательного веса (если такой существует). В этом методе в дополнение к матрице весов С хранится и обновляется вторая -матрица Элемент указывает вершину, непосредственно предшествующую вершине в кратчайшем пути от Матрице присваиваются начальные значения для всех

В соответствии с (8.5) на шаге 3 алгоритма обновление матрицы происходит так:

В конце алгоритма кратчайшие пути получаются непосредственно из заключительной матрицы Таким образом, кратчайший путь между двумя вершинами дается следующей последовательностью вершин:

где

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

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