Теперь займемся вычислением Si исходя из

(в)Докажите, что (при г = 2, 3,..., к) либо Wi(u, v) = 2-и?г 1(и, v), либо Wi(u, v) = 2wi i(u, v) + 1. Выведите отсюда, что

2u i(«,i;) St(u,v) 2St 1(u,v) + \V\ - 1

для всех v £ V.

(г)Для г = 2, 3,..., к и (u,v) £ Е положим

щ(и, v) = Wi(u, v) + 25; i(s, и) - 258 i(s, v).

Покажите, что Wi(u,v) 0.

(д)Пусть Si(s, v) - вес кратчайшего пути относительно весовой функции tbi. Покажите, что

Si(s, v) = Si(s, v) + 258 i(s, v)

и что Si(s, v) \E\.

(е)Объясните, как за время О(Е) вычислить все значения Si(s,v), зная 5i i(s,v). Как вычислить S(s,v) (для всех v £ V) за время 0(£4gTT)?

25-5 Алгоритм Карпа для отыскания цикла с минимальным средним весом

Пусть G = (V, Е) - ориентированный граф с весовой функцией w: Е -> М., и пусть п = \V\. Средним весом (mean weight) цикла с = (ei, б2, • • •, ек), где ej - ребра графа, назовем число

1 к

8 = 1

Пусть li* = ттс Li(c), где с пробегает все (ориентированные) циклы. В этой задаче мы опишем эффективный алгоритм для вычисления Ll*.

Не ограничивая общности, будем считать, что каждая вершина v £ V достижима из некоторой вершины s. Через S(s, v) обозначим вес кратчайшего пути из s в v; пусть 5k(s,v) - вес кратчайшего пути из s в v, состоящего в точности из к рёбер (если такого пути нет, полагаем 5k(s,v) = оо).

(а)Пусть li* = 0. Покажите, что G не содержит циклов отрицательного веса и что S(s, v) = minofcn-i k(s, v) для всех v £ V.

(б)Пусть li* = 0. Покажите, что

Sn(s,v) - Sk(s,v) max--- 0

0<к<п-1П-к

для любой вершины v £ V (Указание: воспользуйтесь двумя утверждениями предыдущего пункта.)

(в)Пусть и и v - две вершины, лежащие на цикле нулевого веса. Пусть вес участка этого цикла от и до v равен ж. Покажите, что S(s, v) = S(s,u) + х (Указание: вес участка от v до и равен - ж).

(г)Пусть ц* = 0. Покажите, что существует вершина v, лежащая на цикле с минимальным средним весом, такая, что

Sn(s, v) - Sk(s, v)

max -1------ = 0

Ofcra-ln - к

(Указание: покажите, что кратчайший путь от s до вершины, лежащей на цикле с нулевым весом, можно продолжить вдоль этого цикла так, что он останется кратчайшим.)

(д)Пусть ц* = 0. Покажите, что

Sn(s, v) - Sk(s, v) mm max--- = 0.

vEV 0<к<п-1П - к

(e) Покажите, что

ц = mm max

8n(s, v) - 8k(s, v)

ev ofcn-in - к

(Указание: если прибавить константу t к весам всех ребер, то ц* увеличится на t.)

(ж) Разработайте алгоритм, вычисляющий ц* за время 0(VE).

Замечания

Алгоритм Дейкстры [55] появился в 1959 году (без упоминания очередей с приоритетами). Алгоритм Беллмана-Форда основан на двух отдельных алгоритмах, изобретённых Беллманом [22] и Фордом [71]. Связь кратчайших путей с ограничениями на разности описана Беллманом. Алгоритм для поиска кратчайших путей в ациклическом ориентированном графе за линейное время описан Лоулером [132] (как »фольклорный»).

Если веса рёбер - небольшие целые числа, то для нахождения кратчайших путей из одной вершины можно применить и более эффективные методы. Ахуджа, Мельхорн, Орлин и Тарьян [6] описывают алгоритм, работающий за время 0(Е + V\J\gW) в предположении, что веса - целые неотрицательные числа, не превосходящие W. Они же приводят простой алгоритм, работающий за время 0(E-\-V\g W). Для случая, когда веса могут быть отрицательными (целыми) числами, есть алгоритм Габоу и Тарьяна [77], работающий за время 0(\/VE\g(VW)), где W - максимум абсолютных величин весов.

Хороший обзор различных алгоритмов, связанных с линейным программированием (в частности, симплекс-метода и метода эллипсоидов), дают Пападимитриу и Стайглиц [154]. Симплекс-метод был изобретён Данцигом (С. Dantzig) в 1947 году, и различные

варианты этого метода до сих пор остаются наиболее популярными способами решения задач линейного программирования. Метод эллипсоидов предложил Л.Г.Хачиян, основываясь на работах Н.З. Шора, Д.Б. Юдина и А.С. Немировского. Кармаркар описывает свой алгоритм в [115].