Алгоритмы - построение и анализ (1021735), страница 147
Текст из файла (страница 147)
Рне. 25.2. Взвешенный ориентированный граф, который используется в упражнениях 25.1-1, 25.2-1 и 25.3-1 Глава 25. Кратчайшие пути между всеми парами вершин 717 25.1-2. Почему требуется, чтобы при всех 1 < 1 < и выполнялось равенство шн = О? О оо оо . оо со О оо оо оо оо О оо использующаяся в алгоритмах поиска кратчайших путей? 25.1-4. Покажите, что матричное умножение, определенное в процедуре ЕХ- темп Бноктезт РАтнБ, обладает свойством ассоциативности.
Покажите, как выразить задачу о кратчайшем пути из единого истока в виде произведения матриц и вектора. Опишите, как вычисление этого произведения соответствует алгоритму, аналогичного алгоритму Беллма- на-Форда (см. раздел 24.1). 25.1-5.
25.1-6. Предположим, что в алгоритмах, о которых идет речь в этом разделе, также нужно найти вершины, принадлежащие кратчайшим путям. Покажите, как в течение времени 0 (пз) вычислить матрицу предшествования П на основе известной матрицы Ь, содержащей веса кратчайших путей. Вершины, принадлежащие кратчайшим путям, можно вычислить одновременно с весом каждого из кратчайших путей. Пусть к," — предшественник вершины з на произвольном пути с минимальйым весом, который соединяет вершины г и у и содержит не более гп ребер.
Модифицируйте процедуры ЕхтенЭ БнОктезт РАтнБ и Бьо~ч Аы. РА)кБ Бноктезт РАтнБ таким образом, чтобы они позволяли вычислять матрицы ПО),П!з),...П!" г) так же, как вычисляются матрицы ЬО),Х1з),..., 1 (и-1) 25.1-7. В процедуре РАБтек Аы. РА)кБ БнОктезт РАтнБ в том виде, в кото- 25.1-8. ром она представлена, требуется хранить !!8 (и — 1)~! матриц, содержащих по пз элементов, для чего требуется общий объем памяти, равный 9 (по18п).
Модифицируйте данную процедуру таким образом, чтобы ей требовалось всего 9 ! пз) памяти для хранения двух матриц размером и х и. Модифицируйте процедуру РАБтек Аы. РА!кБ Бноктезт РАтнБ таким образом, чтобы она была способна выявлять наличие циклов с отрицательным весом. 25.1-9. 25.1-3.
Чему в операции обычного матричного умножения соответствует матрица Часть Ч1. Алгоритмы для работы с графами 718 25.1-10. Разработайте эффективный алгоритм, позволяющий найти в графе количество ребер цикла с отрицательным весом, имеющего минимальную длину. 25.2 Алгоритм Флойда-Варшалла В этом разделе задача о поиске кратчайших путей между всеми парами вершин в ориентированном графе с = (У, Е) будет решаться с помощью различных модификаций динамического программирования.
Время работы полученного в результате алгоритма, известного как алгоритм Флойда-Варшалла (Р!суд-%агйа11 а!8опбпп), равно 9 (Tз). Как и ранее, наличие ребер с отрицательным весом допускается, но предполагается, что циклы с отрицательным весом отсутствуют. Как н в разделе 25.1, будет пройден весь процесс разработки алгоритма в стиле динамического программирования. После исследования полученного в результате алгоритма будет представлен аналогичный метод, позволяющий найти транзитивное замыкание ориентированного графа. Структура кратчайшего пути В алгоритме Флойда-Варшалла используется характеристика структуры кратчайшего пути, отличная от той, которая применялась алгоритмах, основанных на перемножении матриц для всех пар вершин.
В этом алгоритме ~рассматриваются "промежуточные" вершины кратчайшего пути. Промежушочной (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,..., к). Можно дать рекурсивное определение величины я~ ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
