(Е! = Е U {(s,v) : v £ V} и w(s,v) = 0 для всех v £ V). Заметим, что вершина s может быть лишь начальной вершиной в пути (входящих в s рёбер нет). Очевидно, что новый граф G содержит цикл отрицательного веса тогда и только тогда, такой цикл есть в исходном графе G.

На рис. 26.6 (а) показан граф G1, соответствующий графу G рис. 26.1.

Предположим теперь, что граф G (а потому и G) не содержит цикла отрицательного веса. Положим h(v) = S(s,v) для W £ V. Согласно лемме 25.3, для всех рёбер (и, v) £ Е выполнено неравенство h(v) h(u) + w(u,v), которое можно переписать как w(u, v) + h(u) - h(v) 0. Другими словами, новая весовая функция, определённая формулой (26.9), неотрицательна. На рис. 26.6(b) показаны новые веса рёбер графа G рис. 26.6(a).

Вычисление кратчайших путей

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

Запишем соответствующую процедуру. Мы считаем, что граф задан с помощью списков смежных вершин. Процедура возвращает матрицу D = (dij) размера \V\ X \V\, где dij = Sij, или же сообщает о наличии в графе циклов с отрицательными весами. (Мы предполагаем, что вершины графа G пронумерованы от 1 до \V\.)

{\sc Johnson}$(G)$\\

>здать граф $G$, для которого $V[G]=V[G]\cup\{s\}$ и\\ l$E[G]=E[G]\cup\{(s,v):\ v\in V[G]\>$\\ I if {\sc Bellmann-Ford>$(G,w,s)=${\sc false>\\

Ithen print имеется цикл отрицательного веса\\ I else for (для) каждой вершины $v\in V[G]$\\

I do $h(v)\leftarrow\delta(s,v)$,\\

I(значение $\delta(s,v)$ вычислено алгоритмом Беллмана-Форда)\\ for (для) каждого ребра $(u,v)\in E[G]$\\

do $\hat w(u,v)\leftarrow w(u,v)+h(u)-h(v)$\\ I for (для) каждой вершины $u\in V[G]$\\ do {\sc Dijkstra}$(G,\nat w,u)$\\ I(вычисление $\hat\delta(u,v)$ для всех $v\in V[G])$\\ I for (для) каждой вершины $v\in V[G]$\\

I do $d {uv>\leftarrow\hat\delta(u,v)+h(v)-h(u)$\\

•eturn $D$

Рис. 26.5 26.6 Алгоритма Джонсона в применении к графу рис. 26.1. (а) Граф G с исходной весовой функций w. Вспомогательная вершина s - чёрная. Внутри каждой вершины v записано значение h(v) = S(s, v). (b) Каждому ребру (и, v) приписан новый вес w(u, v) = w(u, v) -\-h(u) - h(v). (c)-(g) Результаты работы алгоритма Дейкстры для всех вершин графа G с весовой функщйд w. В каждом случае начальная вершина выделена чёрным. Внутри каждой вершины записаны величины $(и, v)/S(u, v). Вес кратчайшего пути duv = S(u,v) равен S(u, v) + h(v) - h(u).

Эта процедура следует описанной схеме. В строке 1 формируется граф G, затем в строке 2 к нему применяется алгоритм Беллмана-Форда (при этом используется весовая функция w). Если в G (а значит, и в С) есть цикл отрицательного веса, то об этом сообщается в строке 3. Строки 4-11 выполняются, если в графе такого цикла нет. В строках 4-5 вычисляются значения функции h(v) для всех вершин v £ V (веса кратчайших путей S(s, v), найденные алгоритмом Беллмана-Форда). В строках 6-7 вычисляются новые веса рёбер. В строках 8-11 для каждой вершины и £ V[G] вызывается алгоритм Дейкстры и определяются веса кратчайших путей 5(и, v) из этой вершины, а затем они пересчитываются в 5(и, v) по формуле (26.10), и ответ помещается в массиве D.

На рис. 26.6 показан пример выполнения алгоритма Джонсона.

Нетрудно подсчитать, что время работы алгоритма Джонсона составит 0(V2 lg V + VE), еслит использовать фибоначчиеву кучи для хранения очереди с приоритетами в в алгоритме Дейкстры. При более простой реализации очереди в виде двоичной кучи общее время работы составит 0(VElgV), что меньше, чем оценка 0(V3) для алгоритма Флойда-Уоршолла, если только граф достаточно разрежен.

Упражнения

26.3-1 Примените алгоритм Джонсона к графу рис. 26.2, найдя значения haw.

26.3-2 Каким образом используется вспомогательная вершина в в алгоритме Джонсона?

26.3-3 Применим алгоритм Джонсона к графу, в котором исходная весовая функция сама неотрицательна. Что можно сказать о новой весовой функции в этом случае?

26.4* Замкнутые полукольца: общая схема для задач о путях

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

Определение замкнутого полукольца

Замкнутым полукольцом (S, ф, 0,0,1) (по-английски closed semiring) называется множество S с определёнными на нем би-

нарными операциями сложения ф и умножения 0 (в английском оригинале используются термины summary и extension), а также элементами 0,1 £ S, для которого выполнены такие свойства:

1.(S, ф, 0) является моноидом (monoid):

•S замкнуто (is closed) относительно ф, то есть а ф Ь £ S для всех a,b £ S;

•операция ф ассоциативна (is associative): аф (бфс) = (аф&) фс для всех а, 6, с £ 5;

•0 - нейтральный элемент (is an identity) для ф, то есть аф 0 = 0 ф а = а для всех а £ S;

(S, 0,1) также является моноидом;

2.Элемент 0 - аннулятор (annihilator): а©О = О0а = О для всех а £ S;

3.Операция ф коммутативна (is commutative): а ф Ь = Ь ф а для всех a,b £ S.

4.Операция ф идемпотентна (is idempotent): а ф а = а;

5.Операция 0 дистрибутивна относительно ф (distributes over ®): а 0 (6 Ш с) = (й 0 6) ф (а 0 с) и (6 ф с) 0 а = (& 0 й) ф (с 0 й) для всех а, Ь, с.

6.Можно продолжить операцию ф на бесконечные последовательности, задач для любой последовательности а\, а2, а3,... элементов S её сумму агФагФзФ • • £ 5*. При этом нули (элементы 0) в бесконечной сумме можно выкидывать; если при этом она превращается конечную, то должна совпадать с суммой в прежнем смысле.

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

8.Операция 0 дистрибутивна относительно бесконечных сумм: а 0 (6i Ф Ь2 ф Ъ3 ф ...) = (а 0 bt) ф (а 0 Ъ2) Ф (а 0 Ъ3) ф ... и (сц Ф а2 ф а3 ф • • •) 0 Ь = (ai 0 Ь) ф (а2 0 Ь) ф (а3 0 6) ф • • •.

Исчисление путей в ориентированных графах

Замкнутые полукольца, несмотря на столь абстрактное определение, тесно связаны с путями в ориентированных графах. Рассмотрим ориентированный граф G = (V, Е) с заданной на нём функцией разметки (labeling function) А : V X V -> S. Мы будем считать, что эта функция задана не только на рёбрах, но и на любых парах вершин, полагая, что для пар (и, v), не являющихся рёбрами, значение X(u,v) равно 0, так что по существу функция задаётся метками на рёбрах (labels of edges)

Определим теперь понятие метки пути (path label). Именно, для любого пути р = (v\,v2,... , Vk) мы будем называть его меткой А(р)