Пусть с каждым ребром ориентированного графа G = (V, Е) ассоциировано действительное число г (и, v), причём 0 г (и, v) 1. Будем интерпретировать r(u,v) как «надёжность» - вероятность того, что сигнал успешно пройдет по каналу из и в v. Считая, что события прохождения сигнала по различным каналам независимы, предложите алгоритм для нахождения наиболее надёжного пути между двумя данными вершинами.

25-2.5

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> {0,1,..., W - 1}, где W > 0 - целое число. Модифицируйте для данного случая алгоритм Дейкстры так, чтобы он искал кратчайшие пути из данной вершины за время 0(WV + E).

25-2.6

Усовершенствуйте решение предыдущего упражнения, сделав время работы алгоритма равным 0({V-\-E) lgH). (Указание: сколько различных оценок кратчайшего пути для вершин из V\S может встретиться одновременно?)

25.2. Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда (Bellman-Ford algorithm) решает задачу о кратчайших путях из одной вершины для случая, когда весам ребер разрешено быть отрицательными. Этот алгоритм возвращает значение true, если в графе нет цикла отрицательного веса, достижимого из исходной вершины, и false, если таковой цикл имеется. В первом случае алгоритм находит кратчайшие пути и их веса; во втором случае задача кратчайших путей (по крайней мере для некоторых вершин) не существует.

Подобно алгоритму Дейкстры, алгоритм Беллмана-Форда производит релаксацию рёбер, пока все значения d[v] не сравняются с S(s,v) (если все S(s,v) определены).

Bellman-Ford(G,w,s)

1Initialize-Single-Source(G,s)

2for i \gets 1 to V[G]-1

3do for (для) каждого ребра (u,v) \in E[G]

4do Relax(u,v,w)

5for (для) каждого ребра (u,v) \in E[G]

6do if d[v]>d[u]+w(u,v)

7then return \textsc{false}

8return \textsc{true}

На рис. 25.7 показана работа алгоритма Беллмана-Форда для графа с пятью вершинами. После инициализации (строка 1) алгоритм \V\ - 1 раз делает одно и то же: перебирает по разу все

Рис. 25.7 25.7 Алгоритм Беллмана-Форда. Исходная вершина - крайняя левая (z). Оценки кратчайшего пути указаны в вершинах. Серым цветом выделены рёбра (u,v), для которых n[v] = и. В данном примере при каждой итерации цикла в строках 2-4 рёбра подвергаются релаксации в лексикографическом порядке: (u,v), (и,х), (и,у), (v,u), (x,v), (х,у), (y,v), (y,z), (z,u), (z,x). (a) Перед первым обходом рёбер, (б-д) Последовательные состояния после каждой обработки всех рёбер. Значения d на рисунке (д) - окончательные. В данном случае алгоритм Беллмана-Форда возвращает значение true.

рёбра графа и подвергает каждое из них релаксации (строки 2-4). После этого алгоритм проверяет, нет ли цикла отрицательного веса, достижимого из начальной вершины s (строки 5-8; вскоре мы увидим, почему эта проверка позволяет выявить такой цикл).

Время работы алгоритма Беллмана-Форда есть 0(VE), поскольку общее число релаксаций есть 0(VE), стоимость инициализации в строке 1 есть 0(V), а стоимость цикла в строках 5-8 есть О(Е).

Докажем, что алгоритм Беллмана-Форда работает правильно.

Лемма 25.12

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s, не содержащий циклов отрицательного веса, достижимых из s. Тогда по окончании работы процедуры Bellman-Ford равенство d[v] = S(s,v) будет выполняться для всех вершин v, достижимых из s.

Доказательство Пусть р = (s = vo, v\,..., vk = v) - кратчайший путь из s в v. Можно считать, что этот путь не содержит циклов (они только увеличивают вес по предположению), поэтому к \V\ - 1. Докажем индукцией по г, что после г-ой итерации цикла (в строках 2-4) будет выполнено равенство d[vi\ = S(s,Vi): поскольку всего делается \V\ - 1 итераций, лемма будет следовать из этого утверждения и леммы 25.5.

При г = 0 это очевидно, так как d[s] = S(s,s) = 0 при входе в цикл. Пусть после г - 1-ой итерации было <i[t>8 i] = 5(s,u8 i). При г-ой итерации произойдет релаксация ребра (f8-i, vi), после чего по лемме 25.7 установится равенство d[vi\ = S(s,Vi). (Другие релаксации могут также уменьшать d[vi\, но не могут сделать его меньше S(s, иг-).)

Следствие 25.13

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s. Тогда вершина v £ V достижима из s в том и только том случае, когда по окончании работы процедуры Bellman-Ford, применённой к этому графу, оказывается, что d[v] < оо.

Доказательство оставляется читателю (упр. 25.3-2).

Теорема 25.14 (Правильность алгоритма Беллмана-Форда)

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s. Если процедура Bellman-

Ford, примененная к этому графу, возвращает значение true, то в результате её работы для всех v £ V будут выполнены равенства d[v] = S(s,v) и подграф предшественников Gv будет деревом кратчайших путей с корнем s. Если же процедура Bellman-Ford возвращает значение false, то в графе есть цикл отрицательного веса, достижимый из вершины s.

Доказательство Если цикла отрицательного веса, достижимого из вершины s, в графе нет, то в результате работы процедуры Bellman-Ford будем иметь d[v] = S(s,v) для всех v £ V (лемма 25.12 и следствие 25.13); следовательно, граф Gv будет деревом кратчайших путей с вершиной s (лемма 25.9). Коль скоро d[v] = S(s, v) для всех v £ V, из леммы 25.3 следует, что для всякого ребра (и, v) выполнено неравенство d[v] d[u] + w(u, v). Значит, ни одно из условий в строке 6 алгоритма выполнено не будет, и алгоритм возвратит значение true.

Пусть теперь в графе есть цикл отрицательного веса (г>о, v\,..., Vk = vo), достижимый из исходной вершины; нам надо показать, что алгоритм возвратит значение false. В самом деле, если d[vi] + -u?(u8 i, иг) для всех г = 1, 2,..., к, то, склады-

вая эти к неравенств и сокращая d[vi] в обеих частях, получим

О 2~}i=i w(vi-ii vi)i что противоречит выбору цикла. Значит, для некоторого г имеем d[vi\ > <i[t>8 i] + w(vi i, Vi), и алгоритм возвращает значение false. Упражнения

25.3-1 Примените алгоритм Беллмана-Форда к ориентированному графу рис. 25.7, выбрав у в качестве исходной вершины. Рёбра обрабатывайте в лексикографическом порядке; изобразите этапы выполнения алгоритма как на рис. 25.7. Замените вес ребра (у, v) на 4 и проделайте то же самое, выбрав исходной вершиной z.

25.3-2 Докажите следствие 25.13.

25-3.3 Пусть во взвешенном ориентированном графе нет циклов отрицательного веса. Определим число т следующим образом: для каждой пары вершин и, v £ V, для которой существует путь из и в v, найдем минимальное количество ребер в путях минимального веса, идущих из и в v; затем возьмем максимум этих чисел по всем таким парам - это и есть т. Покажите, что в алгоритме Беллмана-Форда достаточно выполнять цикл в строках 2-4 т раз.

25.3-4 Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы и для вершин v, у которых S(s,v) = -оо (как мы помним, такое бывает тогда и только тогда, когда существует путь из s в v, задевающий цикл отрицательного веса), после исполнения алгоритма было установлено правильное значение d[v] = S(s,v) = - оо.

25.3-5 Пусть G = (V, Е) - взвешенный ориентированный граф. Разработайте алгоритм, работающий за время 0(VE) и находящий для каждой вершины v £ V значение S*(v) = ттиеу{5(и, v)}. (В