1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 47
Текст из файла (страница 47)
Алгоритм б.б. Кратчайший путь нз одного источника (алгоритм Дейкстры) Вход. Ориентированный граф 0 (У, Е), источник о, Е *Р' и функция 1, отображающая множество ЕХЕ в множество неотрицательных вещественных чисел. Полагаем 1(ог, от)=+со, если ребро (иь ог), огчьоп не принадлежит графу, и 1(о, о)=0. Выход. Для каждого об'Р' наименьшая сумма меток иа ребрах из Р, взятая по всем путям Р, идущим из о, в о. Мелгод. Строим такое множество Яс:-'Р', что кратчайший путь из источника в каждый узел об5 целиком лежит в Я. Массив Р(о] содержит стоимость текущего кратчайшего пути из о. в и, зза але. задачи с одним источником Рис 5.25.
Граф с помеченными ребрамн. который проходит только через узлы из Я, Алгоритм приведен на рнс. 5.24. П Пример 5.14. Рассмотрим граф, изображенный иа рнс. 5.25. Вначале Я=(оа), Р[оа]=0, а Р[о~]=2, +оо, +оо, 10 для 1=1, 2, 3, 4 соответственно.
При первой итерации цикла в строках 4 — 8 берем го=он поскольку Р[о,]=2 — наименьшее значение для Р. Затем вычисляем Р[оа]=М1Ы(+ос, 2+3)=5 и Р[оа]=М1]ч](!О, 2+7)=9. Последовательность значений для Р и другие вычисления алгоритма 5.6 приведены на рис, 5.26. П Теорема 5.8. Алгоршам 5.6 вычисляет стоимость кратчайшего пути среди всех путей, идущих из о, в любой увел, и занимает 0 (а') времени. Л о к а з а т е л ь с т в о. 1ог-цикл в строках 7, 8 требует 0(а) шагов, столько же шагов требует и выбор ш в строке 5.
В оценке сложности чяЫ!е-цикла в строках 4 — 8 этн процессы преобладают над остальными, в]т]1е-цикл выполняется 0(а) раз, так что общая его сложность равна 0(а'). Строки 1 — 3, очевидно, занимают 0(а) времени. Рис. 5.26. Вычисления алгоритма 5.6 иа графе с рис. 5.25. ГЛ. в. АЛГОРитмы иА ГРАФАХ Рис. 5.27. Пути, идущие в узел щ Чтобы показать корректность, надо доказать индукцией по размеру множества Б, что для каждого ребра эЕБ число 0[э) равно длине кратчайшего пути из и, в п.
Более того, для всех ОЕ У вЂ” Б число 0[о] равно длине кратчайшего пути из о, в о, лежащего целиком (если не считать сам узел э) в Б. Базис. Пусть!Я=1. Кратчайший путь из эе в себя имеет длину О, а путь из о, в э, лежащий целиком (исключая э) в Б, состоит из единственного ребра (о„э). Таким образом, строки 2 и 3 корректно формируют начальные значения массива О. Шаг индукции. Пусть еэ — узел, выбранный в строке 5. Если числа 0[еэ) не равно длине кратчайшего пути из о, в в, то должен быть более короткий путь Р, Этот путь Р должен содержать не.
который узел, отличный от ю и не принадлежащий Б. Пусть и— первый такой узел на Р. Но тогда расстояние от ие до о меньше 0Ы, а кратчайший путь в э целиком (исключая сам узел э) лежит в Б (см. рис. 5.27). Следовательно, по предположению индукции 0[э)(0Ы в момент выбора нг, пришли к противоречию. Отсюда заключаем, что такого пути Р нет и 0[еэ) — длина кратчайшего ПУТИ Иэ Эе В ГЭ. Второе утверждение (о том, что 0Ы остается корректным) очевидно ввиду строки 8.
П Е.т1. ДОМИНАГОРЫ В ОРИЕН1ИРОВАННЫХ АЦИКДИЧЕСКИХ ГРАФАХ: КОМБИНИРОВАНИЕ ПОНЯ1ИЙ В этой главе мы уже познакомились с несколькими приемами, применяемыми для разработки эффективных алгоритмов, например с поиском в глубину и разумным упорядочением вычислений. В гл. 4 изучили много структур данных, полезных для представления множеств, над которыми выполняются различные операции. Эту главу мы закончим примером, иллюстрирующим, как можно строить эффективные алгоритмы, комбинируя структуры данных из гл. 4 с техникой для графов, развитой в данной главе.
Мы будем ззз В.Н. ДОМИНАТОРЫ В ОРИЕНТИРОВАННЫХ ГРАФАХ находить доминаторы в ориентированном ациклическом графе, используя, в частности, алгоритм нахождения М1Ы в свободном режиме, алгоритм объединения непересекающихся множеств и 2-3- деревья вместе с поиском в глубину. Ориентированный граф б= (У, Е) называется корневым для (относительно) узла г, если существуют пути из Г в каждый его узел. В остальной части раздела мы будем предполагать, что б =(У, Е) — корневой ориентированный ациклический граф с кор- НЕМ Г. Узел о называется доминатором узла в, если любой путь из корня в ш проходит через о. Каждый узел доминирует над самим собой, а корень доминирует над каждым узлом.
Множество доминаторов узла и можно линейно упорядочить, расположив их в порядке вхождения в какой-нибудь кратчайший путь из корня в иА Доминатор узла ы, ближайший к нему и отличный от него, называется его непосредственным доминатором. Так как множество доминаторов каждого узла линейно упорядочено, то отношение доминирования можно представить деревом с корнем г, называемым доминаторным деревом для б, Вычисление доминаторов полезно в задаче оптимизации кодов (Ахо, Ульман (1973), Хект П 9731).
Мы построим алгоритм сложности 0(е!Оя е), вычисляющий доминаторное дерево для корневого ориентированного ациклического графа с е ребрами. Основная наша цель — показать, как комбинировать технику этой главы и предыдущей. Алгоритм основан на трех леммах. Пусть 6=(У, Е) — граф и б'=(У', Е') — его подграф. Если (а, Ь) ЕЕ', будем писать а хЬО,Ь. Через =Ц.
и =Эо, будем обозначать соответственно транзитивное и рефлексивно-транзитивное замыкания отношения .-о.. Если (а, Ь) ЕЕ, будем писать а э Ь. Лемма 5.12. Пусть 6=(У, Е) — ориентированный ациклический граф с корнем Г, а Я= (У, Т) — вставное дерево для него с корнем Г, построенное поиском в глубину. Пусть а, Ь, с и е( — такие узлы из У„что а =Эз Ь =Я с =Ьзс!.
Далее, пусть (а, с) и ('Ь, й)— прямые ребра. Тогда замена прямого ребра (Ь, й) прямым ребром (а, й) не меняет доминаторов никакого узла в б (см. рис. 5.28). До к а з а те л ь с т в о. Обозначим через б' граф, полученный при замене ребра (Ь, а) в б ребром (а, й). Допустим, что о— доминатор узла ш в б, но не в б'. Тогда в С' найдется путь Р из Г в в, не содержащий о. Очевидно, что этот путь должен идти по ребру (а, й), поскольку это единственное ребро в б', которого нет в б. Поэтому можно написать Р: Г =>" а ~ й =>А ш. Отсюда следует, что узел о должен лежать на пути а =Я й и что он отличен от а и й.
Если а(о(Ь при нумерации, порождаемой поиском в глубину, то замена ребра а О~ а в Р на путь а => с =Я а дает путь в графе б, ГЛ. З. АЛГОРИТМЫ НА ГРАФАХ / Ь ь о' с с l / Рис. 5.28. Преобразование из леммы 5.!2. идущий нз г в и/ и не содержащий о. Если Ь(о(/(, то замена ребра а => /( в Р на путь а ~з Ь => е( дает путь в графе 6, идущий из г в /о и не содержащий и. Так как а(о(Ь или Ь(о(/(, то найдется путь в 6, идущий из г в Го и не содержащий о; получили противоречие.
Допустим, что о — доминатор узла и в 6', но не в 6. Тогда в 6 найдется путь Р из г в ео, не содержащий о. Так как этот путь ие проходит целиком в 6', то он должен содержать ребро Ь =Ь /(. Следовательно, узел о лежит на пути Ь =>е /( и Ь о с(. Таким образом, в 6' есть путь г =Я а => е(~во, не содержащий узел о; получили противоречие. П Лемма 5.13.
Пусть 6 и Я те же, чпзо и в лемме 5.12, а =>з Ь и (а, Ь) — прямое ребро графа 6. Если в 6 нет прямого ребра (с,/(), для которого с(а и а(Г((Ь, и поперечного ребра (е, Г(), для которого а < Г((Ь, то удаление древесного ребра, входящего в Ь, не меняет доминаторов никакого узла в 6 (см. рис.
5.29). 1//е/и прямых и )ронер япоео пыпя / //е/и пхо//яппх поперечных репер Рис. 5.29. Преобразование из леммы 5.!3. в.н. домннлтоиы в оинантниовлнных гилэлх /Фм еяггяе!ик лгяерееямя леггр о г' Рис. б.зо. Преобраеовииие ив леммы бп4. Д о к аз а тел ь ство. Доказательство аналогично доказательству леммы 5.12. П Лемма 5.14. Пусть О и 8 тг ясе, что и в лемме 5.12, (с, й)— поперечное ребро графа О и Ь вЂ” общий предок для с и й с наибольшим номерам.
Пусть а М(Ы((Ь)(1(а!(а, ег) — прямое ребра и Ь~ег~с)). Если ни в адин узел пути Ь =>з с, отличный от Ь, не входит поперечное ребро, то замена поперечнога ребра (с, й) прямым ребром (а, й) не меняет доминаторов никакого узла в С (см. рис. 5.30). До к а з а тел ь от в о. Обозначим через О' граф, полученный при замене ребра (с, й) в С )>абрам (а, а). Допустим, что ив доминатор узла гг в С, но не в О .
Тогда в О' найдется путь Р из г в ег, ие содержащий а. Понятно, что этот путь должен идти по ребру (а, й). Следовательно, узел о должен лежать на пути а =>3 Ь, проходящем по остовному дереву, ибо в противном случае замена ребра а =р й в Р на а =>4 а нли на а =Я с =р й дала бы путь в О, идущий из г в гс н не содержащий а. Но тогда замена ребра а =р й в Р на а=ри=рзс=рй, где и лежит на пути Ь~3с и и)Ь, дала бы путь в С, идущий из г в ег и не содержащий а; получили противоречие.
Допустим, что и — доминатор узла гг в С', но ие в О. Тогда в С найдется путь Р из г в ег, не содержащий а. Понятно, что Р содержит ребро (с, й). Запишем Р в виде и =>зс ~й ~ з еа. Путь г ~з с должен содержать узел, лежащий на пути а =Я Ь, поскольку нет поперечных ребер, входящих в узлы на пути 5=Я с (исключая узел Ь). Пусть х — такой узел с наибольшим номером, а Р, — участок пути Р от г дох, за которым следует х =Яд, а за ним участок пути Р от й до гс. Пусть Р, — путы ~з а ~ й, за которым гл, а хлгоннтмы нх гелехх следует участок пути Р от 4[ до ш. Если узел о лежит на Р„то он должен лежать и на х =ьэ с[, причем о)х. Если он лежит на Р„ то должен лежать на г =Я а.
Так как а(х, то один из этих путей в С' не содержит о; получили противоречие. С[ Легко показать, что повторное применение преобразований из лемм 5.12 — 5.14 до тех пор, пока возможно, переводит граф 6 в дерево. Так как эти преобразования не меняют отношения доминирования, то окончательное дерево должно быть доминаторным для 6. Зто и будет нашим алгоритмом вычисления доминаторов графа О. Вся хитрость — в построении структуры данных, позволяющей эффективно находить подходящие ребра, к которым надо применять преобразования из лемм 5.12 — 5.14. Говоря неформально, можно сказать, что мы строим домииатор. ное дерево для данного ориентированного ациклического графа С= (У, Е) следующим образом. Сначала поиском в глубину строим в О, отправляясь от корня, соответствующее остовное дерево 5= = (У, Т). Номера узлов графа О меняем на их номера, порожденные поиском в глубину, Затем применяем к С преобразования из лемм 5.12 — 5.14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
