Алгоритмы - построение и анализ (1021735), страница 148
Текст из файла (страница 148)
Если )с = О, то кратчай(ь) ший путь из вершины ( в вершину 7' не содержит промежуточных вершин. Таким образом, (о) ~ ЫП. если 1=7'или гас = со, если ( ф 7' и сску < оо. Если при к > 1 получаем путь с - й - у, где lс ф 7', то выбранный нами предшественник вершины 7' совпадает с выбранным предшественником этой же вершины на кратчайшем пути из вершины (с, все промежуточные вершины которого принадлежат множеству (1,2,...,)с — 1).
В противном случае выбирается тот же предшественник вершины 7, который выбран на кратчайшем пути из вершины с', у которого все промежуточные вершины принадлежат множеству (1, 2,..., /с — Ц. Выражаясь формально, при /с > 1 (/с-1) (ь-)) < (ь-1) (ь-ц сг," если с(,у < с(,.„+ с(„у яе (ь-ц ,(/с-1),(Ь-1),(Ь-1) ЯЬ ЕСЛИ ас > ПС„+ а, (25.7) Вопрос о том, как включить вычисление матрицы П(~) в процедуру Р(.Оуп %АкзнА(.(., предлагается рассмотреть в упражнении 25.2-3 самостоятельно.
На рис. 25.4 показана последовательность матриц П(ь), полученных в результате обработки алгоритмом графа, изображенного на рис. 25.1. В упомянутом упражнении также предлагается выполнить более сложную задачу, — доказать, что подграф предшествования С„; является деревом кратчайших путей с корнем (. Еще один способ реконструкции кратчайших путей представлен в упражнении 25.2-7. Транзнтивное замыкание ориентированного графа Может возникнуть необходимость установить, существуют ли в заданном ориентированном графе С = (К Е), множество вершин которого Ъ" = (1, 2,..., и), пути из вершины ( в вершину ) для всех возможных пар вершин (,7' Е Ъ'. Транзиигивное замыкание (1гапз111те с1озпге) графа С определяется как граф С' = = (К Е*), где Е* = (((, у): в графе О имеется путь из вершины г в вершину Я.
Один из способов найти транзитивное замыкание графа в течение времени Е) (пз) — присвоить каждому ребру из множества Е вес 1 и выполнить алгоритм Флойда-Варшалла. Если путь из вершины ( в вершину 7' существует„то мы получим с(1 < и; в противном случае с(г = оо. Имеется и другой, подобный путь вычисления транзитивного замыкания графа С в течение времени Е) (пз), на практике позволяющий сэкономить время и память. Этот метод включает в себя подстановку логических операций Ч (логическое Глава 25. Кратчайшие пути между всеми парами вершин 723 ИЛИ) и Л (логическое И) вместо использующихся в алгоритме Флойда-Варшалла арифметических операций плп и +.
Определим значение 1," при 1,3, й = = 1,2,..., и равным 1, если в графе С существует путь из вершины 1 в вершину 7', все промежуточные вершины которого принадлежат множеству (1,2,..., Й); в противном случае эта величина равна О. Конструируя транзитивное замыкание С* = (г', Е'), будем помещать ребро (г, 7) в множество Е" тогда и только тогда, югда 1," = 1. Рекурсивное определение величины 1,", построенное по аналогии (ь) (ь) с рекуррентным соотношением (25.5), имеет вид (о) ] О если1~,у и (1,3') Ф Е, ]~ 1 если 1 = 3 или (г, 7) Е Е„ а при /с > 1 выполняется соотношение (ь) (ь-з) ~ (ь-з) (ь-1)) О О \ съ ь3 (25.8) Как и в алгоритме Флойда-Варшалла, матрицы Т(") = ~1,, ~~ вычисляются /(Ю в порядке возрастания /с: ТКАхБ)т!че Сьоязке(С) 1 и — ЩС]] 2 1ог 1 - 1 1о и 3 йо 1ог 3 — 1 1о п 4 йо!1 1 = 7' или (г, 7) Е Е]С] 5 1йеп 1(~) — 1 6 е)ае 1(") — О 7 (огй — 11ои 8 йо 1ог з +- 1 1о п 9 йо$ог7' -11оп 10 ао Р 1(", "Ч (1(" "Л1(".
") о Π—,- (,. 11 ге1пгп Т(п) На рис. 25.5 приведены матрицы Т("), вычисленные процедурой ТкА)чз)т(че С1.оз()кн для приведенного графа. Время работы процедуры Тклнштвн С(.озлил, как и время работы алгоритма Флойда-Варшалла, равно 9 (пз). Однаю на некоторых компьютерах логические операции с однобитовыми величинами выполняются быстрее, чем арифметические операции со словами, представвпощими целочисленные данные.
Кроме того, поскольку в прямом алгоритме транзитивного замыкания используются только булевы, а не целые величины, ему требуется меньший объем памяти, чем алгоритму Флойда-Варшалла. Обьем экономящейся памяти зависит от размера слова компьютера. 724 Часть Ч1. Алгоритмы для работы с графами 1 О О О О 1 1 1 О 1 1 О 1 О 1 1 1 О О О О 1 1 1 О 1 1 1 о 1 О О О о О 1 1 О о Т (о) Т(') = Т(Я) = 1 О О О О 1 1 1 О 1 1 1 1 1 1 1 1 О О О 1 1 1 1 1 1 1 1 1 1 1 1 Т(3) Т(4) Рнс.
25.5. Ориентированный граф н матрицы Т(Я), вычисленные алгоритмом тран- знтнвного замыкания Упражнения 25.2-1. Примените алгоритм Флойда-Варшалла ко взвешенному ориентированному графу, изображенному на рис. 25.2. Приведите матрицы Р("), полученные на каждой итерации внешнего цикла. 25.2-2. Покажите, как найти транзитивное замыкание с использованием методики из раздела 25.1. 25.2-3. Модифнцируйте процедуру Рното %лизнил.
таким образом, чтобы в ней вычислялись матрицы Поо в соответствии с уравнениями (25.6) и (25.7). Дайте строгое доказательство того, что для всех г б У граф предшествования С„( — дерево кратчайших путей с корнем г. (Указание: чтобы показать, что граф С„( — ациклический, сначала покажите, (ь) (/с) что из равенства х; = 1 в соответствии с определением )г," следует, что ((( > (1н + ц)(~.
Затем адаптируйте доказательство леммы 24.16.) ()4) (ь) 25.2-4. Как было показано, для работы алгоритма Флойда-Варшалла требуется объем памяти, равный 6 (и ), поскольку мы вычисляем величины ((„у з ((4) для 1, т', й = 1,2,..., и. Покажите, что приведенная ниже процедура, в которой все верхние индексы просто опускаются, корректна и для ее работы требуется объем памяти 6 (пз): Глава 25. Кратчайшие пути между всеми парами вершин 725 Рьоуп %Акзнлы.'(И~) 1 п — гово [И'] 2 27 -И' 3 $огк — 1гоп 4 йо(огг'+-1(оп 5 йо 1'ог 7' — 1 (о и б 60 6[3 плп ( (В г(Ъ + Ы 7 гетпгп 27 Предположим, что мы модифицируем способ обработки равенства в урав- нении (25.7): 25.2-5. (ь) я, если с(, < Н,„+ Н,- (я-1) (ь-1) (ь-1) (ус-1) ау (ь-1) (ь — з) (я-з) (0-1) яь, если с(; > 0,.„+с(„.
Корректно ли такое альтернативное определение матрицы предшество- вания П? Как с помощью выходных данных алгоритма Флойда-Варшалла устано- вить наличие цикла с отрицательным весом? 25.2-6. В одном из способов, позволяющем восстановить в алгоритме Флойда 25.2-7 25.2-8 25.2-9 Варшалла кратчайшие пути, используются величины ф; при (,7',(с = (ь) = 1,2,...,п, где ф, — промежуточная вершина с наибольшим номером, принадлежащая кратчайшему пути из вершины г в вершину 7', все промежуточные вершины которого принадлежат множеству 11, 2,..., й). Дайте рекурсивное определение величин фу,модифицируйте процеду(ь) ру Р~.оу(> %Анзнлы. таким образом, чтобы в ней вычислялись эти величины, и перепишите процедуру Рк()чт Аи.
РА(кз Бноктнзт РАтн так, чтобы в качестве ее входных данных выступала матрица Ф = (ф; ). Чем матрица Ф похожа на таблицу а, которая используется в задаче о перемножении цепочки матриц, описанной в разделе 15.27 Сформулируйте алгоритм, позволяющий вычислить транзитивное замыкание ориентированного графа С = (У, Е) в течение времени О (У Е). Предположим, что транзитивное замыкание ориентированного ациклического графа можно вычислить в течение времени ( (Щ, (Е)), где ("— монотонно возрастающая функция величин ~Ц и )Е!. Покажите, что время поиска транзитивного замыкания С' = ('(г, Е*) ориентированного графа общего вида С = (1г, Е) равно У ()Ц, (Е)) + О (У + Е*). Часть Ч1.
Алгоритмы для работы с графами 25.3 Алгоритм Джонсона для разреженных графов Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени О (Ъ'з 1к 1' + Ъ' Е). Для разреженных графов в асимптотическом пределе он ведет себя лучше, чем алгоритм многократного возведения матриц в квадрат и алгоритм Флойда-Варшалла.
Этот алгоритм либо возвращает матрицу, содержащую веса кратчайших путей для всех пар вершин, либо выводит сообщение о том, что входной граф содержит цикл с отрицательным весом. В алгоритме Джонсона используются подпрограммы, в которых реализованы алгоритмы Дейкстры и Беллмана-Форда, описанные в главе 24. В алгоритме Джонсона используется метод измеиения веса (гетте1я1зг1пя), который работает следуюшим образом. Если веса всех ребер ы в графе С = (Ч, Е) неотрицательные, можно найти кратчайшие пути между всеми парами вершин, по одному разу запустив алгоритм Дейкстры для каждой вершины.
Если неубывающая очередь с приоритетами реализована в виде пирамиды Фибоначчи, то время работы этого алгоритма будет равно О (1™ 1к Ъ' + 1' Е). Если в графе С содержатся ребра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно просто вычислить новое множество ребер с неотрицательными весами, позволяющее воспользоваться тем же методом. Новое множество, состоящее из весов ребер и, должно удовлетворять двум важным свойствам. 1. Для всех пар вершин и, с Е Ъ' путь р является кратчайшим путем из вершины и в вершину е с использованием весовой функции тс тогда и только тогда, когда р — также кратчайший путь из вершины и в вершину и с весовой Функцией ю. 2. Для всех ребер (и, е) новый вес и (и, и) — неотрицательный. Как вскоре станет понятно, предварительную обработку графа С с целью определить новую весовую функцию и можно выполнить в течение времени О (Ъ' Е).