Задача о кратчайших путях между всеми парами узлов.

В предыдущих параграфах этой главы рассматривались задачи нахождения оптимальных в том или ином смысле путей от неко­торого фиксированного узла до всех остальных узлов сети. Здесь мы рассмотрим задачу построения кратчайших путей между все­ми парами узлов. Под длиной пути, также как и ранее в парагра­фах 1-3, понимаем сумму весов дуг, образующих этот путь. Ясно, что эту задачу можно решать, используя n раз (поочередно для каждого узла) один из описанных ранее алгоритмов нахождения расстояний от фиксированного узла. Таким образом, мы получа­ем алгоритмы сложности O(n⁴) (при использовании алгоритма Форда-Беллмана) и O(n³) для сетей с неотрицательными весами (алгоритм Дейкстры) или для бесконтурных сетей (алгоритм 6.6). Однако, для общего случая сетей с произвольными весами име­ются более эффективные алгоритмы, чем метод, основанный на п-кратном применении алгоритма Форда-Беллмана. Один из та­ких алгоритмов, предложенный в 1962 году Флойдом, мы здесь и разберем.

Пусть сеть G=(V,E,c) задана матрицей весов А, где А| i,j | c(v_i,v_j), и A[i,j]=+∞, если дуги (v_i,v_j) в сети нет.

Обозначим через d_k(i,j) длину кратчайшего пути из v_i и v_j, все промежуточные узлы которого содержатся в множестве {v₁,...,v_k}, то есть содержатся в первых к узлах. Будем считать, что d₁(i,j)=A[i,j]. Пусть d_k(i,j) вычислено для всех i,j=l,...,n, и не­котором k≥1. Докажем равенство

d_k+1(i,j) = min(d_k(i,j), d_k(i,k+l) + d_k(k+l, j)). (6.5)

Действительно, рассмотрим кратчайший v_i-v_j-путь р с проме­жуточными узлами из множества {v₁,…,v_k,v_k+1}. Возможны две ситуации: либо узел v_k+1 входит в этот путь, либо нет.

Если узел v_k+1 не входит в путь р, то, как легко видеть, спра­ведливо равенство d_k+1(i,j)= d_k(i,j).

Если же узел v_k+1 входит в путь р, то разбивая это путь на пути от v, до v_k+1 и от v_k+1 до v_j, получаем два новых пути, все проме­жуточные узлы которых входят во множество {v₁,...,v_k}. По­скольку всякий подпуть кратчайшего пути сам является крат­чайшим путем между соответствующими узлами, то справедливо равенство d_k+1(i,j) = d_k(i,k+l) + d_k(k+l,j)), что завершает обосно­вание равенства (6.5).

Равенство (6.5) позволяет легко вычислять расстояния между всеми парами узлов, последовательно вычисляя для всех пар уз­лов значения d₁(i,j). d₂(i,j),..., d_n(i,j), так как расстояние от v₁ до v_j равно d_n(i,j).

Для нахождения самих кратчайших путей будем использовать аналог неоднократно применявшегося ранее массива ОТЕЦ, а именно, заведем матрицу ПРЕД размера n n, в которой ПРЕД[i,j] дает номер узла, являющегося предпоследним в кратчайшем v_i-v_j- пути (понятно, что последним узлом в таком пути является узел v_j). Если k=ПРЕД[i,j], то, посмотрев значение ПРЕД[i,k], получим следующий узел в v_i-v_j-пути. Таким образом, двигаясь по эле­ментам матрицы ПРЕД, легко построить путь для любой пары узлов.

Детали изложены в алгоритме 6.9, где предполагается, что A[i,i]=0, A[i,j]=+∞, если (v_i,v_j) Е. Еще раз повторим, что неотри­цательность весов дуг не предполагается, но считается, что в сети нет контуров отрицательной длины.

АЛГОРИТМ 6.10 ФЛОЙД

(* Вычисление расстояний между всеми парами узлов *)

Данные: Сеть G=(V,E,c), заданная матрицей весов А[...n, 1...n].

Результаты: Расстояния D[i,j] для всех пар v_i, v_j V. матрица ПРЕД, в которой ПРЕД[v] равно номеру предпоследнего узла в кратчайшем v_i-v_j -пути.

Понятно, что сложность алгоритма 6.10 определяется сложно­стью цикла в строках 5-9, который состоит из трех вложенных циклов, выполняемых n раз каждый. Отсюда следует

Теорема 6.7. Алгоритм Флойда имеет сложность O(n³).

Здесь интересно отметить, что точно такую же сложность имеет алгоритм Форда-Беллмана вычисления расстояний от фик­сированного узла до всех остальных узлов сети. В настоящее время не известен ни один алгоритм вычисления расстояния ме­жду фиксированной парой узлов, который был бы существенно эффективнее (то есть имел бы меньшую вычислительную слож­ность), чем алгоритм вычисления расстояний между всеми пара­ми узлов. Впрочем, неизвестно также существует или нет такой алгоритм.

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

Завершим главу рассмотрением примера, иллюстрирующего работу алгоритма Флойда.

Результаты работы цикла в строках 2-6:

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=1

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=2

D= ПЕРЕД=

Результаты работы цикла в строках 7-13 при k=3

D= ПЕРЕД=

Нетрудно проверить, что обе эти матрицы останутся неизмен­ными в результате работы цикла 7-13 при k = 4. Вот кратчайшие пути для некоторых пар узлов: 2-4: 2-3-1-4; 1-3: 1-2-3; 3-2: 3-1-2.