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