Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 162
Текст из файла (страница 162)
Вычисление весов кратчайших путей в восходящем порядке На основе рекуррентного соотношения (25.5) можно создать приведенную ниже процедуру, предназначенную для вычисления величин е(ч в порядке возрас(й) тания )е. В качестве входных данных выступает матрица И' размером и х п, определенная, как в уравнении (25.1). Процедура возвращает матрицу Р("), содержащую веса кратчайших путей. Р(,Оу0-%АкзнАйй(И') 1 п = И(гочиа 2 Р(0) — Иl 3 $огй = 1(оп 4 Пусть Р(й) = (и',, ) — новая матрица размером и х п 5 1огг'=1(оп б Гог 3' = 1 Со п 7 1(й) . (((й-1) 1(й-1) ~(й-1)) = пип ~;~,,й + 8 гешгв .О(") На рис. 25.4 показаны матрицы Р(й), вычисленные алгоритмом Флойда — Уоршелла для графа, изображенного на рис.
25.1. Время работы алгоритма Флойда-Уоршелла определяется трижды вложенными друг в друга циклами 1ог в строках 3 — 7. Поскольку для каждого выполнения строки 7 требуется время О(1), время работы всего алгоритма составляет 9(пз). Код этого алгоритма так же компактен, как и код алгоритма из раздела 25.1. Он не содержит сложных структур данных, поэтому константа, скрытая в Е)-обозначениях, мала.
Таким образом, алгоритм Флойда-Уоршелла имеет практическую ценность даже для входных графов среднего размера. Построение кратчайшего пути Существует множество различных методов, позволяющих строить кратчайшие пути в алгоритме Флойда — Уоршелла. Один из них — вычисление матрицы Р, содержащей веса кратчайших путей, с последующим конструированием на ее основе матрицы предшествования П. Этот метод можно реализовать таким образом, чтобы время его выполнения было равно 0(пз) (упр.
25.1.6). Если задана мат- Часть ) 1 Алгоритмы длл рабаты с графами 734 ми. 1 1 ми. 1 яь мц хш 2 2 х)ь 3 х)ь м)ь мп. 4 мп. 4 м(ь хп. мш м)ь м)ь 5 мп. 0 3 8 сю -4 сю 0 оо 1 7 оо 4 0 оо оо 2 оо -5 0 сю сс сю сю 6 0 р(а) П (0) 0 3 8 оо — 4 оо 0 сю 1 7 оо 4 0 оо оо 2 5 — 5 0 -2 со оо со 6 0 яь 1 1 яь яь х)ь м)ь 2 2 мц 3 яь м)ь мп.
4 1 4 м)ь 1 м(ь яь м)ь 5 мп. ро) П(п = 0 3 8 4 — 4 оо 0 сю 1 7 оо 4 0 5 11 2 5 -5 0 -2 оо оо оо б 0 мп. 1 1 2 1 м)ьяьяь 2 2 мгь 3 яь 2 2 4 1 4 мп. 1 мп. Хп. М(1 5 мп. р(г) = П(а) 0 3 8 оо 0 со сю 4 0 2 -1 -5 4 -4 1 7 5 11 0 -2 6 0 Мп. 1 1 2 1 2 2 мп. 3 мц 2 4 3 4 мп. 1 м)ь мгь яь 5 мп. р(З) П(3) 0 3 -1 3 0 -4 7 4 0 2 -1 -5 8 5 1 мп. 1 4 2 1 4 мп. 4 2 1 4 3 М)ь 2 1 4 3 4 м(е 1 4 3 4 5 МП. 4 -4 1 -1 5 3 0 -2 6 0 р(4) П(~) = 01-32-4 3 0 -4 1 — 1 7 4 0 5 3 2 — 1 — 5 0 — 2 8 5 1 6 0 ми. 3 4 5 1 4 я). 4 2 1 4 3 яь 2 1 4 3 4 х)ь 1 4 3 4 5 ми.
р(в) п(м— Рнс. 25.4. Последовательность матриц Р(ь) н П(ь), вычисленных алп)ритмом Флойда-Уоргаелла длл графа, иэображенного на рис. 25.1. рица предшествования П, то вывести вершины на указанном кратчайшем пути можно с помощью процедуры Рнгмт-А).).-Р)ыиб-Бноитнбт-РАтн. Матрицу предшествования П можно так же вычислить "на лету", в процессе вычисления в алгоритме Флойда — Уоршелла матриц ь)("). Точнее говоря, вычисляется последовательность мк)риц П(0), П(~),..., П~"), где П = П("), а элемент )г~ ) гт определяется как предшественник вершины 7' на кратчайшем пути из вершины г, все промежуточные вершины которого принадлежат множеству 11, 2,..., Ц.
Можно дать рекурсивное определение величины )г, . Когда Й = О, кратчай(ь) ший путь из вершины т в вершину 7' не содержит промежуточных вершин. Таким Глава 75. Кратчайшие луши менсду всеми ларами вершин 735 образом, (о) ( )чп., если г = 5 или гр,. = со еслигф5иги, <оо. (25.6) / (ь-1) ,(ь-1) <,(ь-)) ~(ь-1) ( я„), если с(сй > с(,„+ с(„ (25.7) Вопрос о том, как включить вычисление матрицы П(ь) в процедуру Е).оуп%ккзнлп., предлагается рассмотреть в упр. 25.2.3 самостоятельно. На рис. 25.4 показана последовательность матриц П("), полученных в результате обработки алгоритмом графа, изображенного на рис.
25.1. В упомянутом упражнении также предлагается выполнить более сложную задачу — доказать, что подграф предшествовання С,; является деревом кратчайших путей с корнем 1. Еще один способ реконструкции кратчайших путей рассматривается в упр. 25.2.7. Транзитивнве замыкание ориентированного графа Может возникнуть необходимость установить, существуют ли в заданном ориентированном графе С = (Ъ; Е), множество вершин которого — И = (1, 2,..., и), пути из вершины 1 в вершину 5' для всех возможных пар вершин (,5 Е )7.
Триизитивное замыкание ((гапябве с1оаше) графа С определяется как граф С* = (17, Е'), где Е* = ((г, )): в графе О имеется путь из вершины 1 в вершину 5) Один из способов найти транзитивное замыкание графа в течение времени (Э(пз) — присвоить каждому ребру нз множества Е вес 1 и выполнить алгоритм Флойда-Уоршелла. Если путь из вершины г в вершину 5 существует, то мы получим г(ц < п; в противном случае г(; = оо. Имеется и другой, подобный путь вычисления транзитивного замыкания графа С в течение времени Е)(пз), на практике позволяющий сэкономить время и память. Этот метод включает в себя подстановку логических операций У (логическое ИЛИ) и д (логическое И) вместо используемых в алгоритме Флойда-Уоршелла арифметических операций тгп и +.
Определим значение (м ()ч) для г',5',)с = 1,2,...,и равным 1, если в графе С существует путь из вершйны 1 в вершину 5„все промежуточные вершины которого принадлежат множеству (1, 2,..., Ц; в противном случае эта величина равна О. Конструируя транзитивное замыкание С* = (17, Е'), будем помещать ребро (г',5) в множество Е' Если при )с > 1 получаем путы й 5', где )с ,-й 5', то выбранный предшественник вершины 5 совпадает с выбранным предшественником этой же вершины на кратчайшем пути из вершины )с, все промежуточные вершины которого принадлежат множеству (1, 2,..., )с — 1).
В противном случае выбирается тот же предшественник вершины 5, который был выбран на кратчайшем пути из вершины (, все промежуточные вершины которого принадлежат множеству (1, 2,..., /с — 1). Выражаясь формально, при Е > 1 Часть ЬЬ Алгормвмы длл работы с графами 736 тогда и только тогда, копза 1,. = 1. Рекурсивное определение величины 1, (ь) (ь) построенное по аналогии с рекуррентным соотношением (25.5), имеет вид (/с) (1-1) Г (/с-1) (ь — 1)) сб сб 1 сь /сг (25.8) Как и в алгоритме Флойда-Уоршелла, мы вычисляем матрицы Т(ь) = (1) ) в порядке возрастания Й.
ТКА)с($1Т!ЧЕ-СЬОЯ1КЕ ((с) 1 и= )С.Ц 2 Пусть Т(0) = ф.)~ — новая матрица размером и х и 0 7 (0)~ Э Гога =11оп 4 Гог у = 1 то п 5 1Г а == 7' или ((, з) б С. Е 6 (О) 7 еЬе1~") = 0 8 Гогlс = 11оп 9 Пусть Т(ь) = ~1~ ~ — новая матрица размером п х и и /(Ю 10 фогт' = 1(оп 11 Гог т' = 1 10 и 12 1(ь) = 1('. ")7~~1(ь "Дт(ь. ") гу гу 1 сь ьу 13 гепггп Т(") На рис. 25.5 показаны матрицы Т(ь), вычисленные процедурой Ткл)сз)т(чеСьоз(лж для приведенного графа. Время работы процедуры Ткана)т(же-Сьо- 1000 1000 1000 1е~ 0111 1с>0111000111 011001100111 1011 1011 1011 Рис.
2ЗД. Ориентированный граф и матрицы 2'1"с, вычисленные алгоритмом транзитивного ьм мыввнил. Глава 25. Кратчайшие пути менсау всеми нарами вершин 737 з((кк, как и время работы алгоритма Флойда-Уоршелла, равно 9(пз). Однако на некоторых компьютерах логические операции с однобитовымн величинами выполняются быстрее, чем арифметические операции со словами, представляющими целочисленные данные. Кроме того, поскольку в прямом алгоритме транзитнвного замыкания используются толью булевы, а не целые величины, ему требуется меньший обьем памяти, чем алгоритму Флойда-Уоршелла. Объем сэкономленной памяти зависит от размера слова компьютера. Упражнения 25.2.2 Примените алгоритм Флойда-Уоршелла ко взвешенному ориентированному графу, изображенному на рис.
25.2. Приведите матрицы Р(~1, полученные на каждой итерации внешнего цикла. 25.2.2 Покажите, как найти транзитивное замыкание с использованием методики из раздела 25.1. 25.2.3 Модифнцируйте процедуру Рвот(з-%лкзнльь таким образом, чтобы в ней вычнслялись матрицы П("1 в соответствии с уравнениями (25.6) и (25.7). Дайте строгое доказательство того, что для всех 1 Е У граф предшествования С,; представляет собой дерево кратчайших путей с корнем г'. (Указание: чтобы показать, что граф С,; ациклическнй, сначала покажите, что из равенства к," = 1 в соот(ь) ветствии с определением к(1 следует, что д, > с(я + га( .
Затем адаптируйте (ь) (ь) (ц доказательство леммы 24.16.) 25.2.4 Как было показано, для работы алгоритма Флойда — Уоршелла требуется объем (ь) памяти, равный 9(пз), поскольку мы вычисляем величины д( 1 для (,7', к 1,2,..., и. Покажите, что приведенная ниже процедура, в которой все верхние индексы просто опущены, корректна н что для ее работы требуется обьем памяти Е(пз), Р(лллР-%АкзнА1л. (И') 1 и = РУ.гоевв 2 2)ее И' 3 аког )с = 1 то и 4 Гог 1 = 1 Го и 5 Гогз' = 1(о и 6 ч(; = ш(п (с(б, с(чь + Аьу) 7 ГЕГНГП лл 24 эви 3726 73л Часть И Алгоритмы длл райоты с графами 25.2.5 Предположим, что мы модифицируем способ обработки равенства в уравнении (25.7): (ь — 1) (1-1) (ь-1) (ь — 1) Корректно ли такое альтернативное определение матрицы предшествования П? 25.2.
6 Как с помощью выходных данных алгоритма Флойда — Уоршелла установить наличие цикла с отрицательным весом? 25.2. 7 В одном из способов, позволяющих восстановить в алгоритме Флойда-Уоршелла кРатчайшие пУти, использУютсЯ величины фг ДлЯ 1,7, Й = 1,2,..., и, тле ф; представляет собой промежуточную вершину с наибольшим номером, принадлежащую кратчайшему пути из вершины 1 в вершину 7, все промежуточные вершины которого принадлежат множеству (1, 2,..., Ц. Дайте рекурсивное определение величин ф,, модифицируйте процедуру Рьоуп-%лкзнльь таким образом, (ь) чтобы в ней вычислялись эти величины, и перепишите процедуру Ркпчт-Ап.- Рл)кл-Бноктлзт-Рлтн так, чтобы в качестве ее входных данных выступала матрица Ф = (ф~" ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
