Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
n единичную матрицу размера Ч. Положим ? A = A G ? E n . Определим булевы степени этой матрицы, используя дизъюнкцию ? в качестве сложения, а конъюнкцию ? в качестве умножения (будем для нее использовать обычную точку Пусть ? A 0 = E n , ? A 1 = ? A, . . . , ? A k+1 = ? A k · Наша процедура построения основана наследующем утверждении. Лемма 6.1. Пусть ? A k = (a (k) ij ) . Тогда в графе G изв имеется путь длины ? в противном случае Доказательство проведем индукцией по Базис. При k = 0 и k = 1 утверждение справедливо по определению и Индукционный шаг. Пусть лемма справедлива для k. Покажем, что она остается справедливой и для k + 1. По определению имеем a (k) i1 a (1) 1j ? . . . ? a (k) ir a (1) rj ? . . . a (k) in Предположим, что в графе G изв имеется путь длины ? k + 1. Рассмотрим кратчайший из таких путей. Если его длина ? k, то по предположению индукции a (k) ij = Кроме того 1 . Поэтому a (k) ij a (1) jj = и a (k+1) ij = 1 . Если длина кратчайшего пути из изв равна k + 1 , то пусть v r его предпоследняя вершина. Тогда изв имеется путь длины k и по предположению индукции a (k) ir = Так как (v r , v j ) ? E , то a (1) rj = 1 . Поэтому a (k) ir a (1) rj = 1 a (k+1) ij = Обратно, если a (k+1) ij = 1 , то хотя бы для одного r слагаемое a (k) ir a (1) rj в сумме равно 1. Если это r = j, то a (k) ij = и по индуктивному предположению в G имеется путь изв длины k . Если же r 6= j, то a (k) ir = и a (1) rj = 1 . Это означает, что в G имеется путь изв длины k и ребро (v r , v j ) ? E . Объединив их, получаем путь изв длины ? k + Из леммы 6.1 непосредственно получаем Следствие 1. Пусть G = (V, E) ориентированный граф с n вершинами, а G ? его граф достижимости. Тогда A G ? = Доказательство. Из определения пути следует, что если в G имеется путь изв, тов нем имеется и простой путь изв длины ? n?1. А по лемме 6.1 все такие пути представлены в матрице Таким образом процедура построения матрицы смежности графа достижимости для G сводится к возведению матрицы в степень n ? 1. Для этого достаточно выполнить ] log n[ возведений в квадрат ? ? A 2 ? ? A 2 2 ? . . . ? где k это наименьшее число такое, что 2 k ? n ? Так как стандартный алгоритм умножения n Ч n матриц можно выполнить за время то мы получили алгоритм вычисления графа достижимости за время O(n 3 log n) . Отметим, что это оценка числа битовых операций. Оказывается, что время вычисления можно улучшить до кубического. Алгоритм Уоршолла Вход: Матрица смежности графа Выход B = A G ? 1. B := A G ; 2. FOR k = 1 TO n DO 3. FOR i = 1 TO n DO 4. FOR j = 1 TO n DO 5. b ij := b ij ? (b ik ? b Теорема 6.1. Алгоритм Уоршолла вычисляет матрицу B = за время Доказательство. Введем вспомогательное понятие l - путь. Определение 21. l - путем изв называется путь v i , v i 1 , v i 2 , . . . , v i k , v в графе G, в котором все внутренние вершины принадлежат множеству {v 1 , . . . , v те. 1 ? i r ? l при ? r ? Доказательстве корректности алгоритма основывается наследующей лемме. Лемма 6.2. Пусть B (l) - матрица, полученная после l выполнений цикла по Тогда b (l) ij = 1 весть- путь изв Доказательство. Используем индукцию по l. При l = 0 матрица B (0) = ив ней представлены все пути, те. пути состоящие из одного ребра. Предположим, что лемма верна для некоторого l ? 0 и докажем, что тогда она верна и для l + 1. Тогда для всех i и j имеем b (l+1) ij = b (l) ij ? (b (l) il ? Если b (l+1) ij = 1 , то b (l) ij = или b (l) il = и b (l) lj = 1 . В первом случае по предположению индукции весть путь изв который является и (l + путем. Во втором случае имеется путь изв и путь изв. Объединив их, получим (l + путь изв Обратно, если весть+ путь изв то либо он не проходит через вершину v ив этом случае b (l) il = 1 , либо он включает v и тогда b (l) il = и b (l) lj = 1 . В обоих случаях b (l+1) ij = 1 43 6.1.1 Кратчайшие пути между всеми парами вершин Рассмотрим теперь нагруженные ориентированные графы, ребрам которых приписаны их длины (веса. Пусть G = (V, E) такой граф, в котором длина ребра e ? E задается функцией c(e) . Предположим, что длины всех ребер неотрицательны. Тогда для любой пары вершин u и v однозначно определена длина ?(u, v) кратчайшего пути изв (если из u нельзя достичь то будем считать, что ?(u, v) = ?). Все алгоритмы определения кратчайших путей между вершинами графа используют явно или неявно следующее простое соображение. Лемма 6.3. Критерий Беллмана Вершина w графа G = (V, E) лежит на кратчайшем пути изв тогда и только тогда, когда ?(u, v) = ?(u, w) + ?(w, Используя туже идею, что ив алгоритме Уоршолла, можно построить эффективный алгоритм для нахождения длин кратчайших путей между всеми парами вершин в нагруженном графе. Исходными данными для этого алгоритма являются длины ребер, представленные в матрице C = (c где c ij = c(v i , v j ) , c ij ? если (v i , v j ) / ? E , то c ij = Результатом алгоритма является матрица D = (d ij ) , в которой d ij = ?(v i , v j ) длина кратчайшего пути изв Алгоритм Уоршолла-Флойда Вход: Выход D 1. D := C; 2. FOR k = 1 TO n DO 3. FOR i = 1 TO n DO 4. FOR j = 1 TO n DO 5. d ij := min{d ij , d ik + d Теорема 6.2. Алгоритм Уоршолла-Флойда строит матрицу кратчайших расстояний за время Доказательство теоремы следует из следующей леммы, аналогичной лемме Лемма 6.4. Пусть D (l) - матрица, полученная после l выполнений цикла по k. Тогда длина кратчайшего пути изв Задача о кратчайших путях из одного источника Пусть G = (V, E) ориентированный граф, для каждого ребера e ? E которого указана его (неотрицательная) длина c(e) ? 0. Тогда длина пути p = v 1 , v 2 , . . . , v определяется как сумма длин ребер, входящих в этот путь c(p) = P k i=1 c(v i , v i+1 ) . Если в G имеется путь из вершины a в вершину b, то имеется и такой путь минимальной длины. Он называется кратчайшим путем изв, а его длина обозначается как ?(a, b). Конечно, может оказаться несколько различных кратчайших путей. Естественно спросить, как узнать длину кратчайшего пути изв и построить его Лучшие известные на сегодняшний день алгоритмы, отвечающие на этот вопрос, решают, на самом деле, более общую задачу построения всех кратчайших путей из одного источника по вершине a найти длины кратчайших путей из a вовсе достижимые из нее вершины и построить для каждой из таких вершин некоторый кратчайший путь из a. Если для каждой вершины v ? V , достижимой из a, зафиксировать один кратчайший путь изв, то получившийся граф будет представлять ориентированное дерево с корнем докажите это. Это дерево называется деревом кратчайших путей из a. 6.2.1 Алгоритм Дейкстры Мы рассмотрим алгоритм построения дерева кратчайших путей и определения их длин, предложенный в г. Е. Дейкстрой. Его идея следующая перед каждым этапом известно множество отмеченных вершин S, для которых кратчайшие пути найдены ранее тогда на очередном этапе к нему добавляется вершина w, с самым коротким путем из a, проходящим по множеству после этого пересчитываются длины кратчайших путей изв оставшиеся вершины из V \ с учетом новой вершины w. Длина текущего кратчайшего пути изв, проходящего по множеству, заносится в ячейку D[v] массива D. В конце работы в этом массиве находятся длины соответствующих кратчайших путей. Для определения дерева кратчайших путей служит массив ОТЕЦ, его элемент ОТЕЦ содержит ссылку на вершину, из которой кратчайший путь приходит в Алгоритм Дейкстры Вход: G = (V, E) ориентированный граф, c(u, v) ? 0 длина ребра (u, v) ? если (u, v) /? E, то считаем, что c(u, v) = ?), и исходная вершина a ? V . 1. S := {a}; % отметить a 2. D[a] := 0; % расстояние от a до a 3. FOR EACH v ? V, v 6= a DO 4. {D[v] := c(a, v); % расстояние от a до v через a 5. IF c(a, v) < ? THEN ОТЕЦ := a ELSE ОТЕЦ := ?}; % === ОСНОВНОЙ ЦИКЛ === 6. WHILE V \ S 6= ? DO % есть неотмеченные вершины 7. { выбрать неотмеченную вершину w с минимальным D[w] ; 8. S := S ? {w} ; % отметить w 9. FOR EACH (неотмеченной) u ? V \ S DO 10. { IF D[u] > D[w] + c(w, u) 11. THEN { D[u] := D[w] + c(w, ОТЕЦ := Пример 14. Рассмотрим работу этого алгоритма на нагруженном графе G с множеством вершин (V = {a, b, c, d, e, f}. Зададим длины дуг матрицей C = (c где элемент c uv = c(u, в частности, c uv = означает отсутствие дуги (u, v). C = ? ? ? ? ? ? ? ? ? ? a b c d e f a 0 25 5 30 ? 75 b 12 0 ? ? 120 20 c ? 15 0 20 45 60 d ? ? ? 0 23 20 e ? ? 75 20 0 20 f 40 15 15 Найдем кратчайшие пути из вершины a до остальных вершин Поэтапную работу алгоритма Дейкстры удобно представлять в виде таблицы, строки которой соответствуют его этапам. Первый столбец номер этапа, второй показывает изменение множества отмеченных вершин S, третий вершину w, добавляемую к S на текущем шаге, четвертый длину кратчайшего пути изв, затем идут столбцы со значениями элементов массивов D и ОТЕЦ ОТЕЦ 65 c a c c c 3. a, c, b d 25 - - 25 50 40 c a c c b 4. a, c, b,d f 40 - - - 48 - c a c d b 5. a, c, b,d, f e 48 - - - - - c a c d b 6. a, c, b, d, f, e 20 5 25 48 40 c a c Таблица 2: Алгоритм Дейкстры на графе Дерево кратчайших путей из вершины a задается массивом ОТЕЦ. Оно представлено наследующем рисунке c b d f e 5 15 20 20 Рис. 24: Дерево кратчайших путей из вершины a в графе Теорема 6.3. Алгоритм Дейкстры строит дерево кратчайших путей из вершины a графа = (V, вовсе достижимые из нее вершины и для каждой такой вершины v определяет длину D[v] = ?(a, v) кратчайшего пути в нее из Время работы алгоритма Дейкстры O(|V Доказательство. . Докажем по индукции, что после каждого этапа алгоритма выполнены следующие условия: а) для любой вершины v ? S величина D[v] равна длине ?(a, v) кратчайшего пути изв б) для любой вершины v ? V \ S величина D[v] равна длине кратчайшего пути изв проходящего по множеству в) для каждой вершины v дерева T , задаваемого массивом ОТЕЦ, длина пути из корня a в v равна Эти три условия, очевидно выполняются после инициализации в строках 1- Предположим теперь что они выполнены перед началом го этапа. Пусть w вершина, добавляемая к S на ом этапе. По предположению, D[w] длина кратчайшего пути изв все вершины которого, кроме w, входят в S. Предположим, что есть другой более короткий путь p изв. Зафиксируем на этом пути первую вершину u, не входящую в S. По выбору p u 6= Поэтому путь p разбивается на две непустые части путь изв и путь изв Но по выбору w мы имеем, что длина p 1 ? D[u] ? Так как длина неотрицательна то длина p ? D[w], те. этот путь не короче пути, представленного в дереве T . Таким образом это длина кратчайшего пути изв. Следовательно, условие (а) выполнено и после го этапа. Рассмотрим теперь произвольную вершину u ? V \ (S ? {w}). Кратчайший путь p изв, проходящий по множеству S ? {w}, либо не включает вершину w ив этом случае его длина равна D[u] ион имеется в текущем дереве T , либо он проходит через w и составлен из кратчайшего пути изв через S, продолженного ребром (w, u). В последнем случае длина пути равна D[w]+c(w, u). Новой строке алгоритма эти величины сравниваются и, если путь через w короче, то его длина становится новым значениием D[u] (строка 11) ион фиксируется в дереве T (строка 12). Следовательно, условия (б) ив) также выполнены после го этапа. Так как после завершения алгоритма S = V , тов завершающем дереве T представлены кратчайшие пути из a вовсе достижимые из нее вершины, а массив D содержит длины этих путей. Значение D[u] = ? указывает на то, что вершина u недостижима из вершины Для оценки времени отметим, что число этапов не превосходит |V |, так как на каждом этапе в S добавляется новая вершина. На каждом этапе поиск вершины w с минимальным значением D[w] и последующий пересчет значений D[v] требует O(|V |) шагов. Отсюда, общее время ограничено O(|V | 2 ) 6.2.2 О реализации алгоритма Дейкстры Приведенная выше оценка сложности O(|V основана на наивной реализации поиска вершины с минимальным значением D[w]. Если реализовать D как очередь с приоритетами, используя фиббоначиевы кучи (см. [4]), то время работы алгоритма Дейкстры будет ограничено величиной. При небольшом числе ребер |E| = o(|V эта оценка по порядку лучше чем O(|V | 2 ) . Разумеется, чтобы добиться ускорения, граф следует представлять не матрицей длин ребер, а списками смежности, включив в них длины ребер. Тогда стр алгоритма можно уточнить. FOR EACH u ? L w ? (V \ В этом варианте для w будут просматриваться лишь смежные с ней неотмеченные вершины из L w и общее число выполнений цикла в стр. 9-12 будет не больше числа ребер Имеются также эффективные реализации алгоритма Дейкстры, использующие верхнюю границу длин ребер C m = max{c ij | 1 ? i, j ? |V |} . В этом случае длина всякого пути в графе не превосходит C m |V | . Р. Дайал (R. Dial) предложил для случая целочисленных длин ребер размещать вершины в процессе работы алгоритма в черпаках. В черпаке B i будут находиться вершины v с текущим значением D[v] = i ( 1 ? i ? C m |V | ). Указатель L будет указывать на первый непустой черпак. При изменении D[v] вершина v будет перемещаться в новый черпак (с меньшим номером. При опустошении черпака значение L увеличивается. Для выполнения этого варианта алгоритма Дейкстры достаточно O(|E| + C m |V |) шагов. В работе [16] предложена версия алгоритма Дейкстры-Дайала DIKDB, оптимизирующая использование памяти. В процессе работы вершины располагаются в черпаках двух видов: верхних и нижних. Фиксируется некоторое число ? нижних черпаков {B i | i = 1, 2, . . . , ?} . Число верхних черпаков U j не превосходит C m |V В верхнем черпаке U j , (L < j ? C m |V находятся вершины v с текущим расстоянием D[v] ? [j?, (j + 1)? ? 1]. А каждая из вершин с D[v] ? [L?, (L + 1)? ? 1] находится в нижнем черпаке B i с i = D[v] ? L?. Когда все нижние черпаки становятся пустыми, L увеличивается и новые нижние черпаки заполняются вершинами из первого непустого верхнего черпака. Приведем возможную реализацию алгоритма DIKDB. В процессе работы над черпаками выполняются операции вставки и удаления элементов-вершин, последовательный просмотр элементов и проверка непустоты. Для их представления можно выбрать двусвязные списки с одним указателем на начало, которые позволяют выполнять указанные операции за время O(1) Алгоритм Вход = (V, E) ориентированный граф, представленный списками смежности вида (w 1 , c(v, w 1 )), . . . , (w k(v) , c(v, w k(v) ) , где w 1 , . . . , w k(v) это все вершины, в которые изведут ребра, а c(v, w i ) целочисленная длина ребра (v, w исходная вершина a ? V , C m длина наибольшего ребра из E и параметр ? размер верхнего черпака (и число нижних. FOR EACH i = 0, . . . , ? ? 1 DO создать пустой черпак B i ; 2. M := [C m |V |/?] + 1 ; % число верхних черпаков. FOR EACH j = 1, . . . , M DO создать пустой черпак U j ; 4. S := {a}; % отметить a 5. D[a] := 0; % расстояние от a до a 6. FOR EACH w ? L a DO 7. {D[w] := c(a, ОТЕЦ := a; 9. IF D[w] < ? THEN ВСТАВИТЬ, w) 10. ELSE {j := [D[w]/?]; ВСТАВИТЬ, w) } 11. } ; 12. L := min{{j |U j 6= ?} ? {M + 1}} ; 13. P := min{{i |B i 6= ?} ? {?}} ; 14. IF P = ? THEN % все нижние черпаки пусты 15. ПЕРЕНЕСТИ-В-НИЖНИЕ(L); % перенос из первого верхнего черпака в нижние ОСНОВНОЙ ЦИКЛ === 16. WHILE P < ? DO % есть неотмеченные вершины := НАЧАЛО(B P ); УДАЛИТЬ(B P , w); % w вершина с минимальным D[w] ; 18. S := S ? {w} ; % отметить w 19. FOR EACH (неотмеченной) u ? L w DO 20. IF D[u] > D[w] + c(w, u) 21. THEN 22. { D[u] := D[w] + c(w, ОТЕЦ := w; 24. IF u ? B i THEN УДАЛИТЬ, u); 25. IF u ? U j THEN УДАЛИТЬ, u); 26. IF D[u] < ? THEN ВСТАВИТЬ, u) 27. ELSE {j := [D[u]/?]; ВСТАВИТЬ, u) } 28. }; 29. L := min{{j |U j 6= ?} ? {M + 1}} ; 30. P := min{{i |B i 6= ?} ? {?}} ; 31. IF P = ? AND L < M THEN % все нижние черпаки пусты 32. ПЕРЕНЕСТИ-В-НИЖНИЕ(L) % перенос из первого верхнего черпака в нижние 33. }. Следующая процедура перемещает вершины из первого непустого верхнего черпака в нижние (пустые) черпаки ПЕРЕНЕСТИ-В-НИЖНИЕ(L) 1. FOR EACH w ? U L DO 2. {i := D[w] ? УДАЛИТЬ, w) ; ВСТАВИТЬ, w)}; 3. L := min{{j |U j 6= ?} ? {M + 1}} ; 4. P := min{{i |B i 6= ?} ? Прокомментируем этот алгоритм. При инициализации в стр вершина-сосед a помещается в нижний черпак, если находится на расстоянии меньше ? от a, ив стр. 10 в верхний черпак, если она находится от a на большем расстоянии. Вовремя работы L указывает номер первого непустого верхнего черпака и может только возрастать. P указывает номер наименьшего непустого нижнего черпака. Если P = ?, то все нижние черпаки пусты. Таким образом, в стр и 31 проверяется непустота нижних черпаков и, если все они пусты, то вызывается процедура ПЕРЕНЕСТИ-В-НИЖНИЕ(L), которая перемещает вершины из первого непустого верхнего черпака в нижние черпаки. При инициализации на создание черпаков требуется O(? + [C m |V шагов. Каждое перемещение вершины в нижних и верхних черпаках в стр. 24-27 связано с рассмотрением входящего в нее ребра. Причем каждое ребро обрабатывается в стр. 19 только один раз. Поэтому общее число указанных перемещений не превосходит |E|. Число перемещений каждой вершины по нижним черпакам не превосходит их числа ?. Поэтому общее число указанных перемещений не превосходит |V |?. Операция переноса вершин из черпака в нижние черпаки в стр. 15 и всегда связана с увеличением L и поэтому может выполняться не более M = [C m |V |/?] раз. При этом каждая вершина может переместиться из верхнего черпака в нижний не более одного раза. Отсюда для времени выполнения алгоритма получаем оценку O(|E| + |V |(? + Выбрав в качестве ? величину ?( ? C m ) , получим следующее утверждение. Теорема 6.4. Алгоритм DIKBD строит дерево кратчайших путей из вершины a графа G = (V, вовсе достижимые из нее вершины и для каждой такой вершины v определяет длину = ?(a, кратчайшего пути в нее из Время работы алгоритма DIKBD O(|E| + |V Пример. Рассмотрим пример применения алгоритма DIKBD к поиску кратчайших путей из вершины a в графе G = ({a, b, c, d, e, f}, E), заданном следующими списками смежности {b : 5, c : 14, d : 16}; L b = {c : 6, d : 10, e : 6, f : 24} ; L c = {b : 2, d : 4, f : 17} ; L d = {f : 15} ; L e = {c : 3, d : 3, f : 17} ; L f = {a : Здесь в списке L v пара u : k означает что длина ребра (v, u) равна c(v, u) = Максимальная длина C m ребра в G равна 24. Выберем ? = 4. Тогда M = [24 ? 6/4] + 1 = Таким образом, в стр. 1-3 создаются 4 нижних черпака B 0 , B 1 , B 2 , и 37 верхних черпаков, U 2 , . . . , При инициализации в стр. 6-13 все нижние черпаки остаются пустыми. Соседи a попадут в три верхних черпака U 1 = {b(5; a)}, U 3 = {c(4; a)}, U 4 = {d(16; здесь в скобках после вершины v указаны текущие значения D[v] и ОТЕЦ. L = 1, P = Затем процедура ПЕРЕНЕСТИ-В-НИЖНИЕ(1) переместит b в U 1 . После этого P = 1, b будет удалена из со значениями D[b] = 5 и ОТЕЦ = a. Затем в цикле в стр. 16-28 будут рассмотрены все соседи b. Они попадут в три вехних черпака U 2 = {c(11; b), e(11; b)}, U 3 = {d(15; b)}, U 7 = {f (29; b)} . После этого L = 2, P = 4 и происходит перенос изв нижние черпаки, на самом деле, обе вершины попадают в B 3 = {c(11; b), e(11; и P = 3. После того, как в основном цикле будут удалены обе вершины из со значениями D[c] = 11, ОТЕЦ = b и D[e] = 11, ОТЕЦ = b и будут рассмотрены их соседи, получим два непустых верхних черпака U 3 = {d(14; e)}, U 7 = {f (28; e)} . P снова равно 4, и L = 3. Затем d перемещается в, а оттуда удаляется со значениями D[d] = 11 и ОТЕЦ = e. После этого L = 7, P = 4 и перемещается в B 0 , а оттуда удаляется со значениями D[f] = 28 и ОТЕЦ = e. На этом работа алгоритма завершается. Построенное алгоритмом DIKBD дерево кратчайших путей из вершины a представлено на рисунке 25. - 1 P P P P P q - Q Q Q Q Q Q s a b e c f d 5 6 6 Рис. 25: Дерево кратчайших путей из вершины a, построенное алгоритмом В упомянутой выше работе [16] проведено сравнение многих алгоритмов поиска кратчайших путей на различных классах графов. Среди 7 рассмотренных там вариантов алгоритма Дейкстры алгоритм DIKBD оказался наиболее эффективными успешно справлялся с поиском кратчайших путей в графах, насчитывающих до 10 вершин Алгоритм Беллмана-Форда Алгоритм Дейкстры требует, чтобы веса всех ребер были неотрицательны (см. задачу 6.6). Но бывают ситуации, когда естественно рассматривать и графы с отрицательными весами ребер. Если в них нет циклов отрицательной длины, то понятие кратчайшего пути из одной вершины в другую определено корректно. Следующий алгоритм позволяет решить задачу о кратчайших путей из одного источника для таких графов. В этом алгоритме, как ив алгоритме Дейкстры, в массиве D для каждой вершины v хранится текущее значение D[v] расстояния от до v, а в массиве ОТЕЦ вершина ОТЕЦ, предшествующая v в текущем пути из Алгоритм основан наследующей простой процедуре ослабления Relax, которая рассматривает ребро (u, v) и пытается уменьшить длину текущего пути изв, заменив его на путь изв, продолженный ребром (u, v). procedure Relax(u, v) 1. IF D[v] > D[u] + c(u, v) THEN 2. {D[v] := D[u] + c(u, ОТЕЦ := Следующий алгоритм основан на двух отдельных алгоритмах, предложенных Р. Беллманом (1958) и Л. Фордом (1962). Он многократно пытается применить процедуру Relax ко всем ребрам графа. Алгоритм Беллмана-Форда procedure Bellman_Ford(G = (V, E), c, v 0 ) 50 1. FORALL v ? V DO 2. {D[v] := ?; ОТЕЦ :=nil;} 3. D[v 0 ] := 0 ; 4. FOR i = 1 TO |V | ? 1 DO 5. FORALL (u, v) ? E DO Relax(u, v); 6. FORALL (u, v) ? E DO 7. IF D[v] > D[u] + c(u, v) THEN return false; 8. return Лемма 6.5. Если в графе G = (V, E) нет циклов отрицательной длины, достижимых из то алгоритм Беллмана-Форда в D[v] возвращает длину кратчайшего пути изв Доказательство. Пусть ? = v 0 , v 1 , . . . , v k = v кратчайший путь изв. Поскольку из недостижимы циклы отрицательной длины, то можно считать, что в этом пути нет циклов. Тогда k ? |V | ? 1. Докажем по индукции, что для каждого i ? k после й итерации цикла в строках 4-5 D[v равно длине ?(v 0 , v кратчайшего пути изв При i = 0 равенство очевидно. Пусть после (й итерации цикла D[v i?1 ] = ?(v 0 , v На й итерации цикла в строке 5 для ребра (v i?1 , v будет вызвана процедура Relax(v i?1 , v Так как в этот момент D[v i?1 ] = ?(v 0 , v и ?(v 0 , v i ) = ?(v 0 , v i?1 ) + c(v i?1 , v i ) = D[v i?1 ] + c(v i?1 , v тов после вызова Relax(v i?1 , v значение D[v i ] = ?(v 0 , v Следствие. Вершина v достижима из алгоритм Беллмана-Форда выдает D[v] < а ОТЕЦ вершина прешествующая v на некотором кратчайшем пути изв Действительно, пусть ОТЕЦ = u. Это значит, что после некоторого вызова процедуры, v) расстояние D[v] становится равными далее не изменяется. По лемме = ?(v 0 , и D[u] = ?(v 0 , Тогда имеется кратчайший путь изв, включающий последнее ребро (u, v). На нем ОТЕЦ = u предшествует Теорема 6.5. 1. Если в графе G = (V, E) нет циклов отрицательной длины, достижимых из v 0 , то алгоритм Беллмана-Форда возвращает true и для всех v ? V D[v] = ?(v 0 , v) - длина кратчайшего пути изв, ОТЕЦ - задает дерево кратчайших путей. Если в графе G = (V, E) есть цикл отрицательной длины, достижимый из v 0 , то алгоритм Беллмана-Форда возвращает false (некорректная задача) Сложность (время работы) алгоритма O(|V Доказательство. Пункт 1 непосредственно следует из леммы 6.5 и следствия из нее. Действительно, если из недостижимы циклы отрицательной длины, то после завершения цикла в в строках 4-5 ни для какого ребра (u, v) ? E не будет выполнено неравенство D[v] > D[u] + c(u, и алгоритм вернет значение Для доказательства пункта 2 предположим, что из достижим цикл отрицательной длины Предположим, что для всех i = 1, 2, . . . , k ? 1 выполнены неравенства i+1 ] ? D[v i ] + c(v i , v i+1 ) . Тогда, сложив все эти неравенства и сократив все D[v слева и справа (заметим, что D[v k ] = D[v 1 ] , получим неравенство 0 ? P k?1 i=1 c(v i , v i+1 ) . Но сумма справа и есть длина цикла, которая по его выбору должна быть отрицательной. Следовательно, хотя бы для одного i неравенство D[v i+1 ] ? D[v i ] + c(v i , v не выполняется. Алгоритм это обнаруживает в строке 7 и возвращает результат Оценка времени очевидна. Отметим, что при большом количестве ребер |E| = O(|V она является кубической относительно числа вершин Пример 15. Рассмотрим работу этого алгоритма на графах и G 2 , показанных на рис. Оба имеют одинаковые множества вершин V 1 = V 2 = {a, b, c, и ребер E 1 = E 2 = {(a, b), (a, c), (a, d), (b, c), (d, b), (c, d)} . Различен лишь вес ребра (c, d). G 1 : a b c d - 10 - -5 ? 20 6 2 @ @ @ @ @ R 5 5 G 2 : a b c d 10 - -10 20 6 2 @ @ @ @ @ R 5 Рис. 26: Ориентированные графы и Работа алгоритма Беллмана-Форда на графе показана в следующей таблице. Ищутся ОТЕЦ c d b c d 1 (a, b) 10 ? ? a - - (a, c) 10 20 ? a a - (a, d) 10 20 5 a a a (b, c) 10 15 5 a b a (d, b ) 7 15 5 d b a (c, d) 7 15 5 d b a 2 (b, c) 7 12 5 d Таблица 3: Алгоритм Беллмана-Форда на графе кратчайшие пути из вершины a. Для i = 1 приведены результаты вызовов процедуры Relax(u, для всех ребер из E, а для i = 2 только для ребра (b, c), так как вызовы для остальных ребер не меняют массивов D и ОТЕЦ. При i = 3 изменений в результатах не происходит. Так как отсутствуют циклы отрицательной длины, тов конце работы массив D задает длины кратчайших путей из a, а массив ОТЕЦ сами эти пути. В графе имеется цикл bcdb отрицательной длины -3, достижимый из a. Работа первой части алгоритма Беллмана-Форда (строки 1-5) на этом графе показана в следующей таблице. В этой таблице при i = 2, 3 показаны только ребра, ослабления по которым изменяют результаты. При провере во второй части алгоритма (строка 7) для ребра (b, c) обнаружится, что D[c] = 12 > D[b] + c(b, c) = 4 + 5 = 9. После этого алгоритм завершится выдачей результата false. 6.2.4 Кратчайшие пути в ациклических графах Отсутствие циклов в графе позволяет за счет выбора топологического порядка перебора ребер строить кратчайшие пути из одной вершины с помощью однократного вызова процедуры Relax для каждого ребра. Алгоритм Кратчайшие пути в ациклическом графе (КПАГ) procedure КПАГ(G = (V, E), c, v 0 ) 52 ОТЕЦ c d b c d 1 (a, b) 10 ? ? a - - (a, c) 10 20 ? a a - (a, d) 10 20 5 a a a (b, c) 10 15 5 a b a (d, b ) 7 15 5 d b a (c, d) 7 15 5 d b a 2 (b, c) 7 12 5 d b a (c, d) 7 12 2 d b a 3 (d, b ) 4 12 2 d Таблица 4: Алгоритм Беллмана-Форда на графе G 2 1. Отсортировать V в топологическом порядке (см. задачу 5.9) 2. Пусть в этом порядке V = u 1 , u 2 , . . . , u и v 0 = u k ; 3. FOR i = k TO n DO 4. {D[u i ] := ОТЕЦ i ] := nil}; 5. D[u k ] := 0 ; 6. FOR i = k TO n DO 7. FORALL (u i , u j ) ? E DO Relax(u i , u Теорема 6.6. Пусть G = (V, E) ориентированный ациклический граф с функцией веса ребер и выделенной вершиной v 0 . Тогда алгоритм КПАГ для каждой достижимой из вершины v возращает кратчайшее расстояние D[v] от до нее, а подграф, заданный массивом ОТЕЦ, является деревом кратчайших путей из Время работы алгоритма КПАГ не превосходит O(|V | + |E|), те. линейно относительно размера графа. Доказательство. Пусть p = (u k = v 0 , u k 1 , . . . , u k r = v) кратчайший путь изв (если таких путей несколько, то пусть p это кратчайший путь с лексикографически минимальной обратной последовательностью индексов (k r?1 , k r?2 , . . . , k 1 ) . Тогда k < k 1 < . . . < k r . Поэтому из ребер пути p в цикле в строках 6 и 7 первым будет рассмотрено ребро (u k , u k 1 ) , после него ребро (u k 1 , u и т.д. Предположим по индукции, что после вызова Relax(u k j?1 , u в строке D[u равно длине ?(u k , u кратчайшего пути p (j) = (u k = v 0 , u k 1 , . . . , u изв и что массив ОТЕЦ зафиксировал этот путь. Тогда при вызове Relax(u k j , u текущее значение k j+1 ] > D[u k j ] + c(u k j , u k j+1 ) = ?(u k , u равенство означало бы, что имеется кратчайший путь изв с лексикографически меньшей чему обратной последовательностью индексов. Поэтому после этого вызова D[u k j+1 ] = D[u k j ] + c(u k j , u k j+1 ) = ?(u k , u k j+1 ) , а ОТЕЦ[u k j+1 ] = u Отсюда по индукции заключаем, что после вызова Relax(u k r?1 , u k r ) D[v] = D[u является кратчайшим расстоянием от до v, а массив ОТЕЦ задает этот кратчайший путь. Для оценки сложности заметим, что топологическая сортировка выполняется с помощью алгоритма ПОГ+ пост за линейное время O(|V | + |E|), цикл в строках 4 и 5 выполняется за шагов, а цикл в строках 6 и 7 требует не более O(|V | + |E|) шагов. У алгоритма КПАГ имеется интересное приложение к задаче управления проектами. Предположим, что имеется большой проект, разбитый на некоторое множество работ. Всему проекту соответствует граф работ, в котором каждая работа представлена ориентированным ребром Все работы, входящие в некоторую вершину должны быть закончены прежде, чем начнется выполнение любой выходящей из нее работы. Из этого следует, что граф работ является ациклическим. Каждой работе сопоставлен вес плановое время ее выполнения. (Вообще говоря, не всякое отношение предшествования работ описывается графом указанного вида. Иногда для его точного задания требуется добавлять фиктивные работы нулевого веса) Одна из основных технологий, применяемых для управления проектами PERT (Project Evaluation and Review Technique) включает нахождение так называемого критического пути самого длинного пути в графе. Содержательно, его длина равна общему времени выполнения проекта при условии максимально возможного распараллеливания работ. Поэтому основное внимание при управлении проектом следует уделять работам, находящимся на критическом пути, а работы не на нем можно и задержать. Поскольку в процессе реализации проекта реальные времена выполнения работ отличаются от плановых, граф работ часто меняется и всякий раз задачу поиска критического пути требуется решать заново. Как это делать Достаточно просто поменять у каждого ребра знак веса на противоположный (отрицательный) и применить алгоритм КПАГ к получившемуся графу Задачи |