Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 149
Текст из файла (страница 149)
") о Π—,- (,. 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.
Для всех ребер (и, е) новый вес и (и, и) — неотрицательный. Как вскоре станет понятно, предварительную обработку графа С с целью определить новую весовую функцию и можно выполнить в течение времени О (Ъ' Е). Сохранение кратчайших путей Как видно из приведенной ниже леммы, легко организовать изменение весов, удовлетворяющее первому из сформулированных выше свойств. Значения весов кратчайших путей, полученные с помощью весовой функции и, обозначены как Б, а веса кратчайших путей, полученных с помощью весовой функции и, — как д.
Лемма 25.1 (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф С = (1г, Е) с весовой функцией ю: Š— В., Глава 25. Кратчайшие пути между всеми парами вершин 727 и пусть Ь: Е -> К вЂ” произвольная функция, отображающая вершины на дей- ствительные числа. Для каждого ребра (и, о) Е Е определим ю(и,о) = ю(и,о)+ Ь(и) — Ь(о). (25.9) Пусть р = (оо, оы..., оь) — произвольный путь из вершины оо в вершину оь. р является кратчайшим путем с весовой функцией ю тогда и только тогда, когда он является кратчайшим путем с весовой функцией ю, т.е. равенство ю(р) = = д (оо, оь) равносильно равенству ю (р) = б (оо, оь).
Кроме того, граф С содержит цикл с отрицательным весом с использованием весовой функции ю тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции ю. Доказательство. Начнем с того, что покажем справедливость равенства ю (Р) = ю (р) + Ь (оо) — Ь (оь) Запишем цепочку соотношений (25.10) ь ю (Р) = ~~ ю (о>-» о>) = >=1 ь (ю(о> ыо;)+ Ь(о; 1) — Ь(о;)) >=1 ь = ~~ 'ю (о;-ыо;) + Ь(оо) — Ь(оь) = >=1 = ю (Р) + Ь (оо) — Ь (оь), ю (с) = ю (с) + Ь (оо) — Ь (оь) = ю (с), где предпоследнее равенство легко получается из "телесюпичностн" суммы разностей. Таким образом, вес любого пути р из вершины оо в вершину оь равен ю (р) = = ю (р)+Ь (оо) — Ь (оя). Если один путь из вершины оо в вершину оь короче другого с использованием весовой функции ю, то он будет короче и с использованием весовой функции ю.
Таким образом, равенство ю(р) = Б(оо,оь) выполняется тогда и только тогда, когда ю (р) = Б (оо, оь). Наюнец, покажем, что граф С содержит цикл с отрицательным весом с использованием весовой функции ю тогда и толью тогда, когда он содержит такой цикл с использованием весовой функции ю. Рассмотрим произвольный цикл с = = (оо, оы..., оь), где оо = оь. В соответствии с уравнением (25.10), выполняется соотношение Часть Ч1. Алгоритмы для работы с графами 728 а следовательно, вес цикла с будет отрицательным с использованием весовой функции ю тогда и только тогда, когда он отрицательный с использованием весовой функции и.
Генерация неотрицательных весов путем их изменения Следующая наша цель заключается в том, чтобы обеспечить выполнение второго свойства: нужно, чтобы величина и (и,п) была неотрицательной для всех ребер (и, и) е Е. Для данного взвешенного ориентированного графа С = (1г, Е) с весовой функцией ю: Š— К мы создадим новый граф С' = (Ъ", Е'), где 1" = У 0 (з) для некоторой новой вершины з ф Ъ' и Е' = Е О ((з, о): с Е Ъ"). Расширим весовую функцию ю таким образом, чтобы для всех вершин ю е У выполнялось равенство тз (з, с) = О. Заметим, что поскольку в вершину з не входит ни одно ребро, эту вершину не содержит ни один кратчайший путь графа С' отличный от того, который исходит из ж Кроме того, граф С' не содержит циклов с отрицательным весом тогда и толью тогда, югда таких циклов не содержит граф С.
На рис. 25.6а показан граф С', соответствующий графу С на рис. 25.1. Теперь предположим, что графы С и С' не содержат циклов с отрицательным весом. Определим для всех вершин о е 1г' величину й(п) = б(з, и). Согласно неравенству треугольника (лемма 24.10), для всех ребер (и, и) Е Е' выполняется соотношение Ь(о) < 6(и) + ю (и,о). Таким образом, если мы определим новые веса в в соответствии с уравнением (25.9), то получим и (и, о) = ю (и, с)+6 (и)— — л (с) > О, так что второе свойство удовлетворяется. На рис. 25.6б показан граф С', полученный в результате переопределения весов графа, изображенного на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
