Общий случай. Алгоритм Форда-Беллмана.

Всюду в дальнейшем будем предполагать, что если узлы v и w не являются смежными в сети G=(V,E,c), то c(v,w)=∞. Для удоб­ства изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем считать, что m>n (т.е. m=Ω(n)). Это исключает ситуации, при которых большинство узлов изолиро­ваны. Кроме того будем рассматривать только такие сети, в кото­рых нет контуров отрицательной длины. Понятно, что если сеть содержит контур отрицательной длины, то расстояние между не­которыми парами узлов становится неопределенным, поскольку, обходя этот контур достаточное число раз, можно построить путь между этими узлами с длиной, меньшей любого, наперед задан­ного, вещественного числа.

Метод решения ЗКП в некотором смысле аналогичен методу построения кратчайшего по числу ребер пути. Вначале размечаем все узлы данной сети (прямой ход алгоритма), вычисляя расстоя­ния от s до всех узлов. Затем, используя значения найденных рас­стояний, обратным ходом строим требуемый путь. Интересно отметить, что для вычисления расстояния от s до t, мы вычисляем расстояния от s до всех узлов сети. В настоящее время не извес­тен ни один алгоритм нахождения расстояния между фиксиро­ванными узлами, который был бы существенно более эффектив­ным, чем известные алгоритмы вычисления расстояний от одного из фиксированных узлов до всех остальных.

Начнем с первого этапа — вычисления расстояний от s до всех узлов. Метод, который мы будем здесь использовать, часто назы­вают динамическим программированием, а алгоритм вычисления расстояний — алгоритмом Форда-Беллмана. Появился этот алго­ритм в работах Форда в 1956 году, и Беллмана — в 1958 году.

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

d₁(v)≥d₂(v)≥ ... ≥d_n-1(v).

Поскольку по предположению в графе нет контуров отрица­тельной длины, то кратчайший s-v-путь не может содержать бо­лее n-1 дуги. Поэтому величина d_n-1(v) дает искомое расстояние от s до v.

Для вычисления d_n-1(v) достаточно последовательно вычислять d_k(v) для всех k=1,…,n-1.

Значения d₁(v) вычисляются просто:

d₁(v) = c(v,w) для всех v V.

Пусть значения d_k(v) вычислены для всех v V. Легко видеть, что для всех k=l,...,n-2 справедливы равенства

d_k+1(v) = min{d_k(v), d_k(w)+c(v,w) : w V}.

Организовать все эти вычисления можно с помощью всего лишь одного одномерного массива D длины n. Положив D[v]=c(s,v) для всех узлов v V, будем иметь равенства

D[v] = d₁(v).

Просматривая после этого все узлы veV, произведем пересчет значений D[v] по формуле

D[v]=min{D[v], D[w]+c(w,v) : w V}. (6.1)

После завершения первого пересчета значений D[v] для всех v из V, будем иметь неравенства D[v] < d₂(v). Почему не равенства? Пусть пересчет начинался с узла v'. Ясно, что тогда D[v'] = d₂(v'). Пусть следующим узлом, для которого был сделан пересчет был узел v". Тогда D[v"] ≤ D[v']+c(v',v"), что вытекает из формулы пересчета (6.1). Отсюда следует, что возможна ситуация, в кото­рой D[v"] = D[v']+c(v',v"), и, кроме того, D[v'] могло быть полу­чено на пути, состоящем из двух дуг. Следовательно, значение D[v"] может быть получено по некоторому пути из трех дуг. Зна­чит D[v"] ≤ d₂(v").

Повторив процесс пересчета D[v] n-2 раза, будем иметь равен­ства D[v]=d_n-1(v), то есть D[v] дает расстояние от s до v. Прежде чем подробнее обосновать равенства D[v] = d_n-1(v), дадим фор­мальное описание алгоритма Форда-Беллмана.

АЛГОРИТМ 6.1. ФОРД-БЕЛЛМАН

(* Нахождение расстояний от фиксированного узла *).

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

Результаты: Расстояния D[v] от s до всех узлов v V.

Напомним, что по определению матрицы весов справедливы равенства A[v,w]=c(v,w) для всех (v,w) E, и, что по нашему со­глашению A[v,w]=∞, если в сети нет дуги (v,w).

Вернемся к обоснованию равенства D[v]=d_n-1(v). Заметим, что при первом входе в цикл, начинающийся в строке 4, справедливы равенства D[v]=d₁(v), для всех v V.

Предположим, что при входе в k-ую итерацию цикла 4, спра­ведливы неравенства D[v]≤d_k(v), для всех v V. Докажем, что по завершению этой итерации справедливы соотношения

D[v]≤d_k+1(v), v V.

Действительно, после выполнения цикла в строке 6 при про­извольном узле v V справедливы неравенства

D[v] ≤ D[w]+A[w,v], для всех w V.

По предположению имеем D[w] ≤ d_k(w). Учитывая, что A[w,v]=c(w,v), получаем неравенства D[v] ≤ d_k(w)+c(w,v), спра­ведливые для всех w V.

В частности, это неравенство справедливо и для того узла w, который является предпоследним в кратчайшем s-v-пути, со­стоящем из k+1 дуги. Отсюда сразу следует справедливость тре­буемого неравенства D[v] ≤ d_k+1(v).

Таким образом, по завершению (n-2)-ой итерации цикла в строке 4 справедливы неравенства D[v] < d_n-1(v), v V. Уже отме­чалось выше, что поскольку сеть не содержит контуров отрица­тельной длины, то d_n-1(v) дает длину кратчайшего s-v-пути. Зна­чит D[v] = d_n-1(v). Тем самым обоснование этого равенства, а вме­сте с ним и обоснование корректности алгоритма Форда- Веллмана, завершено.

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

Ясно, что количество операций в строке 3 пропорционально n. Поскольку цикл в строке 4 выполняется n-2 раза, в строке 5 — n-1 раз, а в строке 6 — nраз, и число выполнений оператора при­сваивания при каждом входе в цикл 6 ограниченно константой, то сложность выполнения цикла, начинающегося в строке 4, есть O((n-2)∙(n-l)∙n)=O(n³).

Заметим, что вычисления в алгоритме Форда-Беллмана можно завершить при таком выходе из цикла по к, при котором не про­исходит изменения ни одного значения D[v], Это может произой­ти и при k < n-2, однако, такая модификация алгоритма не изме­няет существенным образом его сложности, поскольку в худшем случае придется осуществить n-2 итерации цикла по k.

Рис.6.1. Работа алгоритма Форда-Беллмана

Иллюстрирует работу алгоритма Форда-Беллмана рис.6.1. Ве­са дуг даны в скобках. Циклы в строках 5 и 6 выполнялись в по­рядке возрастания номеров узлов.

Рекомендуем читателю провести вычисления для этой сети в предположении, что узел 3 встречается раньше узла 2. В этом случае расстояния будут вычислены за один проход, то есть строки таблицы, соответствующие всем значениям k, будут оди­наковыми.

Итак, с помощью алгоритма Форда-Беллмана можно вычис­лить расстояния D[v] от s до всех узлов v V. Построение крат­чайшего пути от s до некоторого фиксированного узла t V осно­вано на следующем простом утверждении.

Лемма 6.1.Пусть для некоторого s-t-пути р: s=v₀,v₁,...,v_k=t выполнены равенства

D[v_i]=D[v_i-1]+c(v_i-1, v_i),i=l,2,...,k. (6.2)

Тогда путь p является кратчайшим s-t-путем в сети G.

Поскольку D[v] равно длине кратчайшего s-v-пути, то доста­точно доказать равенство c(p)=D[t].

Перепишем равенства (6.2)в виде c(v_i-1, v_i)=D[v_i]-D[v_i-1]и про­суммируем их по i=l,...,k. Получим равенство

∑{c(v_i-1, v_i): i=l,...,k} = ∑{( D[v_i]-D[v_i-1]): i=l,...,k}

Левая часть этого равенства равна по определению с(p), а пра­вая, как нетрудно видеть, равна D[v_k], то есть D[t]. Отсюда c(p)=D[t].

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

При формальном описании алгоритма построения кратчайше­го s-t-пути, будем использовать функцию ВЫБОР(v), значением которой является такой узел w V, что D[v]=D[w]+A[w,v].

АЛГОРИТМ 6.2. ПОСТРОЕНИЕ КРАТЧАЙШЕГО ПУТИ.

Данные: Сеть G=(V,E,c), заданная матрицей весов А, расстояния D[v] от фиксированного узла s до всех остальных узлов v V, фиксированный узел t.

Результаты: СТЕК, содержащий кратчайший s-t-путь.

Для оценки вычислительной сложности алгоритма 6.2 заме­тим, что цикл в строках 3-8 в худшем случае проработает n раз. Каждая итерация этого цикла обращается к функции ВЫБОР(v).

Понятно, что для поиска вершины w под условием D[v]=D[w]+A[w,v] приходится, вообще говоря, просмотреть все вершины. Поэтому сложность вычисления значения функции ВЫБОР(v) есть О(n). В худшем случае эту функцию придется использовать п-1 раз. Отсюда следует, что алгоритм 6.2 имеет сложность O(n²).

Функция ВЫБОР играет в алгоритме 6.2 ту же роль, что и пе­ременная ОТЕЦ в алгоритмах построения путей с использовани­ем процедур поиска в глубину или в ширину (глава четвертая). Однако, в тех алгоритмах вычисление переменной ОТЕЦ шло в ходе размечивания вершин. В алгоритме Форда-Беллмана можно поступать таким же образом. Для этого строку 6 алгоритма 6.1 достаточно заменить на следующие четыре строки:

6.1. forw Vdo

6.2. ifD[v]>D[w]+A[w,v]then

6.3. beginD[v]:=D[w]+A[w,v]; OTEЦ[v]:=w;

6.4. end;

Разумеется, в строке 3, где вычисляются первоначальные зна­чения переменных D[v] нужно добавить запись ОТЕЦ[v]:=s. По­нятно, что при таких изменениях в алгоритме 6.2 строку 5 нужно заменить на такую строку:

5.1. v:=ОТЕЦ[v];

Легко видеть, что эти изменения не меняют оценку сложности алгоритма Форда-Беллмана, но сложность алгоритма 6.2 по­строения пути становится равной О(n).

Редкие сети (m<<n²), удобнее представлять не матрицей ве­сов А, а списками смежностей СЛЕД[v] или ПРЕДШ[v]. Для вы­числения расстояний от фиксированного узла s до всех осталь­ных узлов редкую сеть удобнее представлять списками ПРЕДШ[v]. В этом случае в алгоритме 6.1 строку 6 следует заме­нить на

6'. forw ПРЕДШ[v]doD[v]:=min(D[w], D[w]+c(w,v)).

В таком случае алгоритм Форда-Беллмана нахождения рас­стояний (алгоритм 6.1) будет иметь вычислительную сложность O(mn), так как каждая дуга анализируется не более одного раза.