Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 161
Текст из файла (страница 161)
25.1. Ориентированный траф и последовательность матриц Ь( ), вычисляемых процедурой зьо(и-Аы.-РА(ка-зноктьат-рлтиа. Можно лепя) убедиться в том, что величина Ь(а) = Ь(ь) И' равна Ь(~), а следовательно, для всех т ) 4 выполняется равенство ю(ы) = ь(~). ЯьО%-А ЕЕ-РА!К3-БНОКТЕзт-РАТНЗ 1И' ) 1 п = И'.гоюл 2 Х(1)=И 3 Хогт= 21оп — 1 4 Пусть У.( '1 — новая матрица размером и х и 5 Х(~1 = Ехтен()-БнОктезт-РАтн31Х(~ 1, И~) б гетпгп Л1" 11 На рис. 25.1 приведены граф и матрицы Х,( 1, вычисленные процедурой Беоч)- АЕЕ-РА1К3-3 НОКТЕ3Т-РАТН8. Улучшение времени работы Однако наша цель состоит не в том, чтобы вычислить все матрицы Х (~1: нам нужна только одна матрица — Х(" 11.
Напомним, что если циклы с отрицательным весом отсутствуют, из уравнения 125.3) вытекает равенство Х( 1 = Х( для всех целых и) > и — 1. Матричное умножение, определенное процедурой Ехтен()-бноктезт-РАтнз, как и обычное матричное умножение, является ассоциативным 1упр. 25.1.4). Таким образом, матрицу Х,1" ') можно получить путем о з — з 3 0 -4 7 4 0 2 -1 — 5 8 5 1 2 — 4 1 — 1 5 11 0 — 2 6 0 0 3 8 З О вЂ” 4 сю 4 0 2 — 1 -5 8 оо 1 О 1-З 3 0 — 4 7 4 0 2 — 1 -5 8 5 2 — 4 1 7 5 11 О -2 6 0 2 — 4 1 -1 5 З о -г 6 0 729 Глава 25.
Краишавшие луши меивду вввии варами вершин вычисления )'18(п — 1)1 матричных умножений в последовательности Е() =И г (г) И г Е(4) !4;в г(8) И 8 = И' ИГ, Игг, Игг И,4 Иг4 (гпв( — и) И глм — и И г('в<"-т- гпн — и- РАБтек-Аьь-РА! кБ-йнОктезт-РАтнБ (И' ) ! п = И'.гвидо 2 ь(1) = Иг 3 т=1 4 иЫ!ет < и — 1 5 Пусть Ь(г ) — новая матрица размером и х п 6 Ь( ~) = Ехтенп-бнОктезт-РАтнБ(ь(~), ь(~)) 7 т=2т 8 гетигп Ь( В каждой итерации цикла ччййе в строках 4-7, начиная с т = 1 вычисляется магг рица Ь(г ) = (ь(™)) . В конце каждой итерации значение т удваивается.
В последней итерации матрица Ь(" ') вычисляется путем фактического вычисления матрицы л.(г ) для некоторого значения п — 1 < 2т < 2п — 2. Согласно уравнению (25.3) Ь(г ) = Ь(" л). Далее выполняется проверка в строке 4, значение т удваивается, после чего выполняется условие т ) п — 1, так что условие цикла оказывается невыполненным, и процедура возвращает последнюю вычисленную матрицу. Поскольку каждое из (18(п — 1)1 матричных произведений требует времени чз(п ), процедура РАБтек-Аьь-РА(КБ-8ноктезт-РАтнБ выполняется за время 9(п~ 18 п). Заметим, что код процедуры довольно компактен. Он не содержит сложных структур данных, поэтому константа„скрытая в Е)-обозначении, невелика.
Упражнении 25.1.1 Выполните процедуру Яьо)ч-Аьь-РА)КБ-8ноктезт-РАтнБ над взвешенным ори- ентированным графом, показанным на рис. 25.2, и запишите промежуточные мат- рицы, которые получаются в каждой итерации цикла. Затем проделаите то же самое для процедуры РАБтек-Аьь-РА)КБ-Яноктезт-РАтнБ.
Поскольку 2((8( з)1 ) п — 1 последнее произведение Е(г ) равно Е(" г). В приведенной ниже процедуре указанная последовательность матриц вычисляется методом многократного возведения е кендрогн (гереа(ед зппаппй). Часть 12 Алгоритмы аале работы с ееагбами 750 Рис. 25.2. Взвешенный ориентированный граф к упр. 25.1.1, 25.2.1 и 25.3.1. 25.1.2 Почему требуется, чтобы при всех 1 < з < и выполнялось равенство зо11 = О? 25.1.3 Чему в операции обычного матричного умножения соответствует матрица О со со. ° ° со оо О оо .. со оо ос О .
со используемая в алгоритмах поиска кратчайших путей? 25.1.4 Покажите, что матричное умножение, определенное в процедуре Ехтв1ч11- ЗНОКтият-РЛтНЗ, обладает свойством ассоциативности. 25.1.5 Покажите, как выразить задачу о кратчайшем пути из единого истока в виде произведения матриц и вектора. Опишите, как вычисление этого произведения соответствует алгоритму, аналогичного алгоритму Беллмана-Форда 1см.
раздел 24.1). 25.1.б Предположим, что в алгоритмах, о которых идет речь в этом разделе, нужно также найти вершины, принадлежащие кратчайшим путям. Покажите, как за время 01пз) вычислить матрицу предшествования П на основе известной матрицы весов кратчайших путей 1.. 25.1.7 Вершины, принадлежащие кратчайшим путям, можно вычислить одновременно с весом каждого из кратчайших путей.
Определим зг," как предшественник вершины 5 иа произвольном пути с минимальным весом, который соединяет вершины з и з и содержит не более т ребер. Модифицируйте процедуры Ехтв1е0-Зноктйзт-Рлтнз и Бьотч-Аьь-Рл1из-Бноктизт-Рлтнз таким образом, чтобы они позволяли вычислять матрицы П11), П12),..., П1" О наряду с матрицами А~1),1~2),...,А~и 1). 737 /лава 75.
Кратчайшие аути мввсду всеми варами вершим 25.1.8 В процедуре Глзтпк-Аи.-Рл!яз-Бноптпзт-Рлтиз в том виде, в котором она представлена, требуется хранить (1б(п — 1)1 матриц, содержащих по и элементов, для чего требуется общий объем памяти, равный !В(па 1я п). Модифицируйте данную процедуру таким образом, чтобы ей требовалось только !В(пз) памяти, используя для работы только две матрицы размером о х и. 25.1.9 Модифицируйте процедуру Глзтеп-Ап.-Рл!кз-Яноктпзт-Рлтнз таким образом, чтобы она была способна выявлять наличие в графе циклов с отрицательным весом. 25.1.10 Разработайте эффективный алгоритм, позволяющий находить в графе количество ребер минимального по длине цикла с отрицательным весом.
25.2. Алгоритм Флойда-Уоршелла В этом разделе задача о поиске кратчайших путей между всеми парами вершин в ориентированном графе С = (1', Я) будет решаться с помощью различных подходов динамического программирования. Время работы полученного в результате алгоритма, известного как алгоритм Флойда-Уоршаша (Р!оуб-%ага!за!! а!яопг!пп), равно !В(!'з).
Как и ранее, наличие ребер с отрицательным весом допускается, но предполагается, что циклы с отрицательным весом отсутствуют. Как и в разделе 25.1, нами будет пройден весь процесс разработки алгоритма в стиле динамического программирования. После исследования полученного в результате алгоритма будет представлен аналогичный метод для поиска транзитивного замыкания ориентированного графа. Структура кратчайшего пути В алгоритме Флойда — Уоршелла используется характеристика структуры кратчайшего пути, отличная от рассмотренной в разделе 25.1. В этом алгоритме рассматриваются промежуточные вершины кратчайшего пути.
Промежулвочиой (!пгеппесйаге) вершиной простого пути р = (щ, сз,..., сс) является любая вершина р, отличная от с1 и тп т.е. любая вершина множества (сз, пз,, .., сс Алгоритм Флойда — Уоршелла основан на следующем наблюдении. Предположим, что граф С состоит из вершин 1с = (1,2,..., и). Рассмотрим подмножество вершин (1,2,...,/с) для некоторого lс. Для произвольной пары вершин в',5 е !7 рассмотрим все пути из вершины 1 в вершину з, все промежуточные вершины которых выбраны из множества (1,2,..., й). Пусть среди этих путей р— путь с минимальным весом (этот путь простой). В алгоритме Флойда — Уоршелла используется взаимосвязь между путем р и кратчайшими путями нз вершины 1 в вершину з, все промежуточные вершины которых принадлежат множе- 732 Часть 12 Алгоритмы для работы с графами Все промежуючные вершины из (1, 2,..., )с — 1) Все промежуточные вершины ю (1, 2,..., )с — 1) р: Все промежуючные вершины из (1, 2,..., (с ) Рис.
25.3. Путь р является кратчайшим путем из вершины с в вершину 2, а )с — промежуточная вершина р с наибольшим номером. Все вершины пути ры являющегося частью пути р из вершины с в вершину )с, приналлежш множеству (1,2,...,)с — 1). То же самое относится и к пути рз из вершины (с в вершину 2. ству (1,2,..., и — Ц. Зта взаимосвязь зависит от того, является ли вершина к промежуточной на пути р.
° Если )с не является промежуточной вершиной пути р, то все промежуточные вершины этого пути принадлежат множеству (1, 2,..., /с — Ц. Таким образом, кратчайший путь из вершины з в вершину 2 со всеми промежуточными вершинами из множества (1,2,...,/с — Ц одновременно является кратчайшим путем из вершины з в вершину 2 со всеми промежуточными вершинами из множества (1, 2,..., Й). ° Если и является промежуточной вершиной пути р, то этот путь, как видно из рнс.
25.3, можно разбить следуюшим образом: т' Ю и Р3 2. Согласно лемме 24.1 р1 является кратчайшим путем из вершины з в вершину и, все промежуточные вершины которого принадлежат множеству (1, 2,..., к). Поскольку )с не является промежуточной вершиной пути рг, все промежуточные вершины этого пути принадлежит множеству (1, 2,...,/с — Ц. Следовательно, р1 является кратчайшим путем от з до )2, все промежуточные вершины которого принадлежат множеству (1, 2,..., )с — Ц. Аналогично рз — кратчайший путь из вершины )2 в вершину 2, все промежуточные вершины которого принадлежат множеству (1, 2,..., )с — Ц, Рекурсивное решение задачи о кратчайших путях между всеми парами вершин Определим на основе сделанных выше наблюдений рекурсивную формулировку оценок кратчайших путей, отличную от той, которая использовалась в разделе 25.1.
Пусть с(1 — вес кратчайшего пути из вершины с в вершину 2, для (ь) которого все промежуточные вершины принадлежат множеству (1, 2,..., (с). Если й = О, то путь из вершины с в вершину 2, в котором отсутствуют промежуточные вершины с номером, ббльшим нуля, не содержит промежуточных вершин вообще. Такой путь содержит не более одного ребра, следовательно, с(,, = асс . (о) Рекурсивное определение, которое соответствует приведенному выше описанию, 733 Глава 23. Кратчайшие лути между всеми нарами вершин задается соотношением Поскольку все промежуточные вершины произвольного пути принадлежат множеству (1,2,..., п), матрица Р(") = (о, ~) дает окончательный ответ: и', ) = д((,3) для всех пар вершин (,3 Е Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
