Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 148
Текст из файла (страница 148)
Структура кратчайшего пути В алгоритме Флойда-Варшалла используется характеристика структуры кратчайшего пути, отличная от той, которая применялась алгоритмах, основанных на перемножении матриц для всех пар вершин. В этом алгоритме ~рассматриваются "промежуточные" вершины кратчайшего пути. Промежушочной (1п1еппед(аде) вершиной простого пути р = (ш, оз,..., Ш) называется произвольная вершина, отличная от щ и оп т.е. это любая вершина из множества (оз, оз,..., и~ 1). Алгоритм Флойда-Варшалла основан на следующем наблюдении.
Предположим, что граф С состоит из вершин У = (1, 2,..., и). Рассмотрим подмножество вершин (1, 2,..., 1г) для некоторого 1г. Для произвольной пары вершин 1,,1 б У рассмотрим все пути из вершины 1 в вершину з', все промежуточные вершины которых выбраны из множества (1,2,..., Ц. Пусть среди этих путей р— путь с минимальным весом (этот путь простой). В алгоритме Флойда-Варшалла используется взаимосвязь между путем р и кратчайшими путями из вершины 1 в вершину з, все промежуточные вершины которых принадлежат множеству (1, 2,..., й — Ц.
Эта взаимосвязь зависит от того, является ли вершина й промежуточной на пути р. ° Если 1с — не промежуточная вершина пути р„то все промежуточные вершины этого пути принадлежат множеству (1, 2,..., 1с — Ц. Таким образом, кратчайший путь из вершины 1 в вершину з' со всеми промежуточными вершинами из множества (1, 2,..., й — Ц одновременно является кратчайшим путем из вершины 1 в вершину з со всеми промежуточными вершинами из множества (1, 2,..., Й). Глава 25. Кратчайшие пути между всеми парами вершин 719 Бзе ар"выехало:ныз а.таю а Б ч пьечзхна зы веапюа ь ~ ~~- Бмаа ххтачаеммаааааааа меха~!Ь2....,к~ Рис.
25.3. Схема, иллюстрирующая структуру кратчайших пугей ° Если )с — промежуточная вершина пути р, то этот путь, как видно из рис. 25.3, можно разбить следующим образом: г' - к - )'. Согласно лемР1 Рз ме 24.1, р1 — кратчайший пугь из вершины г в вершину Й, все промежуточные вершины которого принадлежат множеству (1,2,..., Й). Посюльку й не является промежуточной вершиной пути рм понятно, что р1 — кратчайший путь из вершины г в вершину Й, все промежуточные вершины которого принадлежит множеству (1, 2,..., )с — 1).
Аналогично, рз — кратчайший путь из вершины Й в вершину 3, все промежуточные вершины юторого принадлежат множеству (1, 2,..., и — 1). Рекурсивное решение задачи о кратчайших путях между всеми парами вершин Определим на основе сделанных выше наблюдений рекурсивную формулировку оценок кратчайших путей, отличную от той, которая использовалась в разделе 25.1.
Пусть Н, — вес кратчайшего пути из вершины г в вершину з, для 1ь) которого все промежуточные вершины принадлежат множеству (1, 2,..., Й). Если к = О, то путь из вершины г в вершину 3, в котором отсутствуют промежуточные вершины с номером, большим нуля, не содержит промежуточных вершин вообще. Такой путь содержит не более одного ребра, поэтому Н," = ю; . Рекур(о) сивное определение, которое соответствует приведенному выше ойисанию, дается соотношением ив если )с = О, Н, = г1ь П <ь О 1ь От (25.5) ппп ~Ы,", Йь +Й„у ) если Й > 1.
о з Поскольку все промежуточные вершины произвольного пути принадлежат множеству (1, 2,..., и), матрица 23;з ~ = (Н,"~) дает юнечный ответ: <ф) = б (г, з) для всех пар вершин г,3 Е Ъ'. Часть Ч1. Алгоритмы для работы с графами 720 Вычисление весов кратчайших путей в восходящем порядке Исходя из рекуррентного соотношения (25.5), можно составить приведенную ниже процедуру, предназначенную для вычисления величин с(; в порядке воз(я) растания )с. В качестве входных данных выступает матрица Иг размерами и х и, определенная в уравнении (25.1). Процедура возвращает матрицу Р("), содержащую веса кратчайших путей. Рьоуп %лнзнлЩИ') 1 и +- гоюз)И'] 2 Р(0) < — И/ 3 $огй -1 топ 4 Йо(огг 11оп 5 аоЬ 7 1то 6 ао (,'.,".") пап(((ь "', (ьь "+ (ьт ") 7 гетигп Р(") На рис.
25.4 приведены матрицы Р(ь), вычисленные алгоритмом Флойда-Варшалла для графа, изображенного на рис. 25.1. Время работы алгоритма Флойда-Варшалла определяется трижды вложенными друг в друга циклами 1ог, определенными в строках 3-6. Поскольку для каждого выполнения строки 6 требуется время 0(1), алгоритм завершает работу в течение времени 6 (и ). Код этого алгоритма такой же компактный, как и код алгоритма, представленного в разделе 25.1. Он не содержит сложных структур данных, поэтому константа, скрытая в Е)-обозначениях, мала. Таким образом, алгоритм Флойда-Варшалла имеет практическую ценность даже для входных графов среднего размера. Построение кратчайшего пути Существует множество различных методов, позволяющих строить кратчайшие пути в алгоритме Флойда-Варшалла. Один из них — вычисление матрицы Р, содержащей веса кратчайших путей, с последующим конструированием на ее основе матрицы предшествования П.
Этот метод можно реализовать таким образом, чтобы время его выполнения было равно О (пз) (упражнение 25.1-6). Если задана матрица предшествования П, то вывести вершины на указанном кратчайшем пути можно с помощью процедуры Ринг Аьь Рлщз Бноктнзт Рлтн.
Матрицу предшествования П можно так же вычислить "на лету", как в алгоритме Флойда-Варшалла вычисляются матрицы Р(~). Точнее говоря, вычисляется последовательность матриц П(е), П(1),..., П("), где П = П("), а элемент к(. (ь) Глава 25. Кратчайшие пути между всеми парами вершин 721 8 оо — 4 Хп. ХП.
2 оо 1 7 П(0)— Р(о) О оо оо -5 О оо ХИ. ХП. Хп. ХИ. оо 6 О ХП. Хп. Хп. ХИ. 8 оо — 4 Хп. Хп. 2 П(!) = Хп. х!ь ХП. ХИ. р(я) П(л)— со 6 О ХП. ХП. Хп. 8 4 — 4 со 1 7 О ХП. П(3)— Р(а) Хп. Хп. ХИ. — 1 4 -4 -4 1 -1 ПРО = 7 4 2 -1 8 5 — 3 2 -4 — 4 1 — 1 П(а) = Р(а)— 7 4 г 8 5 Рнс. 25.4. Последовательность матриц Р(ь) и П("), вычисленная алгоритмом Флойда-Варшалла для графа, приведенного на рис. 25.1 О 2 О 4 5 4 — 1 оо со 1 7 О оо со — 5 Π— 2 оо 6 О 8 4 — 4 со 1 7 О 5 11 -5 Π— 2 О 5 11 — 5 О -2 со 6 О О 5 3 — 5 О -2 1 6 О О 5 3 — 5 Π— 2 1 6 О х)ь х[ь 4 х)ь Хп.
4 ХП. ХИ. 4 Хп. Хп. 4 ХП, 4 4 4 4 ХП. 4 4 4 4 ХП. 3 ХП. ХП. 3 1 х)ь з 1 хп. 3 3 1 3 з 3 з Хп. з 3 з Хп. Хп. 4 х!ь ХП. 4 Хп. ХП. 4 ХП. Хп. 4 4 4 ХП. 4 4 4 4 ХП. 4 4 ХП. Хп. 5 2 2 2 Хп. 5 2 г 2 х)ь 5 2 2 г ХП. 5 5 2 г ХП. 5 ХП. 1 ХП. 1 2 2 1 1 2 2 1 Хп. 1 1 1 1 х)ь 1 1 1 1 ХП. Часть Ч1. Алгоритмы для работы с графами определяется как предшественник вершины 7' на кратчайшем пути из вершины 1, все промежуточные вершины которого принадлежат множеству (1, 2,..., к).
Можно дать рекурсивное определение величины я~ ). Если )с = О, то кратчай(ь) ший путь из вершины ( в вершину 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)) О =О ~,~си ь) (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(".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
