Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 160
Текст из файла (страница 160)
Чтобы решить задачу о поиске кратчайших путей между всеми парами вершин со входной матрицей смежности, необходимо вычислить не только вес каждого из кратчайших путей, но и матрицу иредшествовения (ргебесеззог шагпх) П = (гг, ), где величина гг; имеет значение ннл если 1 = г или путь из вершины г в вершину г отсутствует; в противном случае зг — предшественник вершины г на некотором кратчайшем пути из вершины г'. Точно так же, как описанный в главе 24 подграф предшествования С„является деревом кратчайших путей для заданного истока, подграф, индуцированный 1-й строкой матрицы П, должен быть деревом кратчайших путей с корнем г'.
Определим для каждой вершины г б И иодгреф яредгиествовеиия (ргебесеззог зпЬйгарЬ) графа С для вершины г как граф С„; = (\Г 1, Е„,), где Части 'гх Алгоритмы дла работы с графами 724 Чтобы подчеркнуть важные особенности представленных в этой главе алгоритмов поиска кратчайших путей между всеми парами вершин, создание матриц пред- шествования и их свойств не будет рассматриваться здесь так же подробно, как в главе 24 в случае подграфа предшествования.
Основные моменты предлагается рассмотреть в некоторых упражнениях. Краткое содержание главы В разделе 25.1 представлен алгоритм динамического программирования, основанный на операции умножения матриц, который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин. С помощью многократного возведения в квадрат можно сделать так, чтобы время работы этого алгоритма было равно 9($'з 1я Ъ'). В разделе 25.2 приведен другой алгоритм динамического программирования — алгоритм Флойда — Уоршелла (г(оуб — ЪагзЬаП).
Время работы этого алгоритма равно 9(17з). В этом же разделе исследуется задача поиска транзитивного замыкания ориентированного графа, связанная с задачей о поиске кратчайших путей между всеми парами вершин. Наконец в разделе 25.3 представлен алгоритм Джонсона. В отличие от других алгоритмов, описанных в этой главе, в алгоритме Джонсона применяется представление графа в виде списка смежных вершин.
Этот алгоритм позволяет решить задачу о поиске кратчайших путей между всеми парами вершин за время 0(Ъ'з 1к 1'+ $'Е), что делает его пригодным для больших разреженных графов. Перед тем как продолжить, нам нужно принять некоторые соглашения для представлений в виде матрицы смежности. Во-первых, в общем случае предполагается, что входной граф С = (17, Е) содержит и вершин, так что и = ~Ъ'~. Вовторых, будет использоваться соглашение об обозначении матриц прописными буквами, например И', Е или гг, а их отдельных элементов — строчными буквами с нижними индексами, например гоц, 15 или г(о. Возле некоторых матриц будут приведены заключенные в скобки верхние индексы, указывающие на количество выполненных итераций, например ь1 1 = (1,.
) или гл1 ) = (г(, ). Наконец для заданной матрицы А размером п х п предполагается, что значение и хранится в атрибуте А. гово. 25.1. Задача о кратчайших путях и умножение матриц В этом разделе представлен алгоритм динамического программирования, предназначенный для решения задачи о поиске кратчайших путей между всеми парами вершин в ориентированном графе С = (17,Е). В каждом основном цикле динамического программирования будет вызываться операция, очень напоминающая матричное умножение, поэтому такой алгоритм будет напоминать многократное умножение матриц.
Начнем с того, что разработаем для решения задачи о кратчайших путях между всеми парами вершин алгоритм со временем работы 9(17~), после чего улучшим этот показатель до величины 9()го 1к 17). Глава 25. Кратчайшие пути между всеми парами вершин 725 Перед тем как продолжить, кратко напомним описанные в главе 15 этапы разработки алгоритма динамического программирования. 1. Описание структуры оптимального решения. 2.
Рекурсивное определение значения оптимального решения. 3. Вычисление значения оптимального решения восходящим методом. (Этап 4, состоящий в составлении оптимального решения на основе полученной информации, рассматривается в упражнениях.) Структура кратчайшего пути Начнем с того, что охарактеризуем структуру оптимального решения. Для задачи о кратчайших путях между всеми парами вершин графа С = ((', Е) доказано (лемма 24.1), что все подпути кратчайшего пути — также кратчайшие пути.
Предположим, что граф представлен матрицей смежности И' = (есе ). Рассмотрим кратчайший путь р из вершины 1 в вершину 5 и предположим, что этот путь содержит не более т ребер. Если циклы с отрицательным весом отсутствуют, то значение т конечно. Если( = 5, то вес пути р равен О, а ребра в нем отсутствуют. Если же вершины 1 и 5 различаются, то путь р раскладывается на 1- lс -+ 5', где р' путь р' содержит не более т — 1 ребер. Согласно лемме 24.1 р' — кратчайший путь из вершины 1 в вершину )с, поэтому выполняется равенство б(в, 5) = б(г, )с) + щ, .
Рекурсивное решение задачи о кратчайших путах между всеми парами вершин Пусть теперь 1," — минимальныи вес любого пути из вершины 1 в вершину 5, (т) содержащий не более т ребер. Если т = О, то кратчайший путь из вершины 1 в вершину 5 существует тогда и только тогда, когда 1 = 5'. Таким образом, (о) ( О, если(=5', ( оо, если( ~ 5'. Для т > 1 величина 1, вычисляется как минимум двух величин.
Первая из них — 1," (вес кратчайшего пути иэ вершины 1 в вершину 5, состоящего не (п1 — Ц более чем из т — 1 ребер), а вторая — минимальный вес произвольного пути из вершины ( в вершину 5, который состоит не более чем из т ребер.
Этот минимальный вес получается в результате рассмотрения всех возможных предшественников )с вершины 5. Таким образом, мы можем рекурсивно определить 1( ) =ппп 1( ), ппп ~1( )+шь.~ (25.2) Последнее равенство следует иэ того, что ш, = О для всех 5. Часть ) Х Алгоритмы дла работы с графами 72б (25.3) Вычисление весов кратчайших путей в восходящем порядке Используя в качестве входной матрицу Иг = (пг,г), вычислим ряд Матриц 1 (~), Л(з),..., Х,(" '), где для иь = 1,2,...,п — 1 имеем Х,( ) = (1,„). Конечная матрица Х(" 1) содержит фактический вес каждого из кратчайших путей.
Заметим, что для всех вершин 1, ) Е Ъ' выполняется равенство 11. = шчь так что г.(1) = Иг. (1) Сердцем алгоритма является приведенная ниже процедура, которая на основе заданных матриц Ь( ') и И' вычисляет и возвращает матрицу Х,( ). Другими словами, она расширяет вычисленные на текущий момент кратчайшие пути, добавляя в них еше по одному ребру. Ехтенп-йноатезт-рлтнз(Х, И' ) 1 и = Х.гона 2 Пусть Х' = (1,' ) — новая матрица размером и х п 3 Гог 1' = 1 Го п 4 1ог 2' = 1 Го п 5 Г =со ч 6 Хогй = 1гоп 7 1', = ппп(1,',1,ь+ гоь ) 8 геФпгп Ь' В этой процедуре вычисляется матрица Х' = (11 ), которая и возвращается процедурой по завершении работы.
Вычисления осуществляются на основе уравнения (25.2) для всех пар индексов 1 и 2; при этом в качестве Х( 1) используется матрица Ь, а в качестве Ь( ) — матрица Х'. (В псевдокоде верхние индексы не используются, чтобы входные и выходные матрицы процедуры не зависели от т.) Из-за наличия трех вложенных циклов 1ог время работы алгоритма равно 9(пз).
Теперь становится понятной связь с умножением матриц. Предположим, требуется вычислить матричное произведение С = А . В, где А и  — матрицы размером и х и. Тогда для 1, ) = 1, 2,..., п мы вычисляем и аья Ьь 1=1 (25.4) Чему равен фактический вес каждого из кратчайших путей б(1,2)? Если граф не содержит циклов с отрицательным весом, то для каждой пары вершин 1 и 2, для которых справедливо неравенство б(1,2) ( оо, существует кратчайший путь из вершины 1 в вершину 2, который является простым и, следовательно, содержит не более п — 1 ребер. Путь из вершины 1 в вершину 2, содержащий более п — 1 ребер, не может иметь меньший вес, чем кратчайший путь из вершины 1 в вершину 21 Поэтому фактический вес каждого из кратчайших путей определяется равенствами Глава 25.
Кратчайшие пути между всеми парами вершин 727 Заметим, что если выполнить замены 1(т — 1) щ — +Ь, 1(™) -+ с, ППП вЂ” 1 + Б(1()яке-МАтк!х-М(л.т!Р1х(А, В) 1 п = А.говда 2 Пусть С вЂ” новая матрица размером и х и 3 1огв = 1(оп 4 Гогз'=1(оп 5 с, =0 6 1ог к = 1 (о и 7 с; = с„+ац,.Ьь 8 ге(пгп С Возвращаясь к задаче о кратчайших путях между всеми парами вершин, вычислим веса кратчайших путей путем поэтапного расширения путей ребро за ребром. Обозначив через А В матричное "произведение", которое возвращается процедурой Ехтпы()-Бноктпзт-РАтнз(А, В), вычислим последовательность и — 1 матриц е (1) е (о) . (4с лв (2) ле (1) и, 7 (з) 7 (2) )4с = И', И72 )4лз ле (п — 1) В(и-2) (47 Или-1 Как было показано ранее, матрица Ь(п 1) = И'" 1 содержит веса кратчайших путей. В приведенной ниже процедуре эта последовательность вычисляется за время 9(п ).
в уравнении (25.2), то получится уравнение (25.4). Таким образом, если в процедуре Ехтп)()з-Бнокткзт-Рлтнз провести соответствующие изменения, а также заменить значение оо (исходное значение для операции вычисления минимума) значением О (исходное значение для вычисления суммы), получится процедура для непосредственного перемножения матриц со временем выполнения 6(пз), которую мы уже видели в разделе 4.2. Часть Ей Алгориатмы ь)лл работы с графами 728 О 3 8(ю — 4 оо 0 оо 1 7 сю 4 0 оо сю -5 О ° сю оо сю 6 0 5(о Еы)— 5(а) т (4) Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
