Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 146
Текст из файла (страница 146)
Оба алгоритма используют объем памяти, зависящий от размера слова машины, на которой выполняется алгоритм. Хотя объем использующейся памяти может оказаться неограниченным в зависимости от размера входных данных, с помощью рандомизированного хеширования его можно снизить до линейно зависящего от размера входных данных. Для неориентированных графов с целочисленными весами Торуп [298] привел алгоритм со временем работы 0 (Ъ'+ Е), предназначенный для поиска кратчайших путей из одной вершины. В отличие от алгоритмов, упомянутых в предыдущем абзаце, этот алгоритм — не реализация алгоритма Дейкстры, поскольку последовательность значений, возвращаемых вызовами процедуры Ехтклст Мпч, не является монотонно неубывающей.
Для графов, содержащих ребра с отрицательными весами, алгоритм, предложенный Габовым (ОаЬо~ч) и Таржаном [104], имеет время работы 0(тЯЕ18(Ъ'Ъ7)), а предложенный Гольдбергом (Оо1дЬегй) [118] выполняется в течение времени 0 (~ТЕ 18 И~), где И' = шах(ь 4 ел ([тс (" с) О. Черкасский (СЬегкаазку), Гольдберг (Оо!дЬегй) и Радзик (йа<Ы1с) [57] провели большое количество экспериментов по сравнению различных алгоритмов, предназначенных для поиска кратчайших путей.
ГЛАВА 25 Кратчайшие пути между всеми парами вершин В этой главе рассматривается задача о поиске кратчайших путей между всеми парами вершин графа. Эта задача может возникнуть, например, при составлении таблицы расстояний между всеми парами городов, нанесенных на атлас дорог. Как и в главе 24, в этой задаче задается взвешенный ориентированный граф С = = (КЕ) с весовой функцией ш: Е -> 8., отображающей ребра на их веса, выраженные действительными числами.
Для каждой пары вершин и, е б 1' требуется найти кратчайший (обладающий наименьшим весом) путь из вершины и в вершину е, вес которого определяется как сумма весов входящих в него ребер. Обычно выходные данные представляются в табличной форме: на пересечении строки с индексом и и столбца с индексом о расположен вес кратчайшего пути из вершины и в вершину и. Задачу о поиске кратчайших путей между всеми парами вершин можно решить, ~Ъ'~ раз запустив алгоритм поиска кратчайших путей из единого истока, каждый раз выбирая в качестве истока новую вершину графа. Если веса всех ребер неотрицательные, можно воспользоваться алгоритмом Дейкстры.
Если используется реализация неубывающей очереди с приоритетами в виде линейного массива, то время работы такого алгоритма равно О (1~з + УЕ) = О (1'з). Если же неубывающая очередь с приоритетами реализована в виде бинарной неубывающей пирамиды, то время работы будет равно О (~' Е 1к У), что предпочтительнее для разреженных графов. Можно также реализовать неубывающую очередь с приоритетами как пирамиду Фибоначчи; в этом случае время работы алгоритма равно О (1'"з 1к Ъ' + УЕ). Глава 25. Кратчайшие пути между всеми парами вершин 709 Если допускается наличие ребер с отрицательным весом, алгоритм Дейкстры неприменим.
Вместо него для каждой вершины следует выполнить алгоритм Беллмана-Форда, который работает медленнее. Полученное в результате время работы будет равно 0 (1гзЕ), которое на плотных графах можно записать как О (И4). В этой главе станет понятно, как лучше поступить. Будет также исследована связь задачи о кратчайших расстояниях между всеми парами вершин с умножением матриц, и изучена алгебраическая структура этой задачи. В отличие от алгоритмов поиска кратчайшего пути из фиксированного истока, в которых предполагается, что представление графа имеет вид списка смежных вершин, в большей части представленных в этой главе алгоритмов используется представление в виде матрицы смежности. (В алгоритме Джонсона (1оЬпзоп) для разреженных графов используются списки смежных вершин.) Для удобства предполагается, что вершины пронумерованы как 1,2,..., ~Ц, поэтому в роли входных данных выступает матрица Иг размером и х и, представляющая веса ребер ориентированного графа С = (г', Е) с п вершинами.
Другими словами, Иг = (ш,"), где 0 если г = 7, вес ориентированного ребра (г,7') если г ~ 2 и (г,7) е Е, (25.1) 00 если г ф 2 и (г,7') ф Е. Наличие ребер с отрицательным весом допускается, но пока что предполагается, что входной граф не содержит циклов с отрицательным весом. Выходные данные представленных в этой главе алгоритмов„предназначенных для поиска кратчайших путей между всеми парами вершин, имеют вид матрицы П = (г(г ) размером п х и, где элемент г(г содержит вес кратчайшего пути из вершины г в вершину ~. Другими словами, если обозначить через б(г', з') кратчайший путь из вершины г в вершину з' (как это было сделано в главе 24), то по завершении алгоритма г(г = б (г, з'). Чтобы решить задачу о поиске кратчайших путей между всеми парами вершин со входной матрицей смежности, необходимо вычислить не только вес какдого из кратчайших путей, но также и матрицу яредглествования (ргебесеааог шаптх) П = (я;"), где величина я;" имеет значение мп., если г = у или путь из вершины г' в вершину 7' отсутствует; в противном случае х; — предшественник вершины г' на некотором кратчайшем пути из вершины г.
Точно так же, как описанный в главе 24 подграф предшествования С„является деревом кратчайших путей для заданного истока, подграф, индуцированный г-й строкой матрицы П, должен бьгть деревом кратчайших путей с корнем г'. Определим для каждой вершины г Е 1~ лодграф лредшествовалил (ргебесеззог зпЬягарЬ) графа С для вершины г как граф С„,; = (К,,;, Е„,;), где Часть Ч1. Алгоритмы для работы с графами 710 Е; = ((яд,3): 3 е К,; — (г)) . Если С„; — дерево кратчайших путей, то приведенная ниже процедура, представляющая собой модифицированную версию описанной в главе 22 процедуры Ркп4т Рлтн, выводит кратчайший путь из вершины 1 в вершину 32 Рщнт Аы.
Рл|кз Бноктцзт Рлтн(П,1,3) 1 1г" 1= 3 2 1пеп рпп! 1 3 е!ае Ыя;, =ни. 4 1пеп рпш "Не существует пути из" 1 "в"' 5 5 еие Ркпчт Аы. Рыка Бноктпзт Рлтн(П,г,я;,) б рппг з' Чтобы подчеркнуть важные особенности представленных в этой главе алгоритмов поиска кратчайших путей между всеми парами вершин, создание матриц предшествования и их свойств не будет рассматриваться здесь так же подробно, как это было в главе 24 в случае подграфа предшествования.
Основные моменты предлагается рассмотреть в некоторых упражнениях. Краткое содержание главы В разделе 25.1 представлен алгоритм динамичесюго программирования, основанный на операции умножения матриц, юторый позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.
С помощью метода "многократного возведения в квадрат" можно сделать так, чтобы время работы этого алгоритма было равно 9 (Уз 1я У). В разделе 25.2 приведен другой алгоритм динамичесюго программирования — алгоритм Флойда-Варшалла (Р)оуо-%агзпаП). Время работы этого алгоритма равно О (Уз). В этом же разделе исследуется задача поиска транзитивного замыкания ориентированного графа, связанная с задачей о поиске кратчайших путей между всеми парами вершин. Наконец, в разделе 25.3 представлен алгоритм Джонсона. В отличие от других алгоритмов, описанных в этой главе, в алгоритме Джонсона применяется представление графа в виде списка смежных вершин. Этот алгоритм позволяет решить задачу о поиске кратчайших путей между всеми парами вершин за время О (Уз 1я У + 'УЕ), что делает его пригодным для больших разрешенных графов. Перед тем как продолжить, нужно принять некоторые соглашения для представлений в виде матрицы смежности.
Во-первых, в общем случае предполагается, что входной граф С = (У, Е) содержит и вершин, так что и = Щ. Вовторых, будет использоваться соглашение об обозначении матриц прописными буквами, например, 1У, Ь или 23, а их отдельных элементов — строчными буквами с нижними индексами, например, ю;, 1г или сг . Возле некоторых матриц Глава 25. Кратчайшие пути между всеми парами вершин 711 будут взятые в скобки верхние индексы, указывающие на количество итераций, например, Ь1 1 = (1,'"~) или Р1 1 = (ф~).
Наконец, для заданной матрицы А размером и х п предполагается, что значение п хранятся в атрибуте гоша [А). 25.1 Задача о кратчайших путях и умножение матриц В этом разделе представлен алгоритм динамического программирования, предназначенный для решения задачи о поиске кратчайших путей между всеми парами вершин в ориентированном графе С = (1г, Е). В каждом основном цикле динамического программирования будет вызываться операция, очень напоминающая матричное умножение, поэтому такой алгоритм будет напоминать многократное умножение матриц.
Начнем с того„что разработаем для решения задачи о кратчайших путях между всеми парами вершин алгоритм со временем работы 9 (1 "4), после чего улучшим этот показатель до величины 9 (Ъ'з 1я Ъ"). Перед тем как продолжить, кратко напомним описанные в главе 15 этапы разработки алгоритма динамического программирования.
1. Описание структуры оптимального решения. 2. Рекурсивное определение значения оптимального решения. 3. Вычисление значения, соответствующего оптимальному решению, пользуясь методом восходящего анализа. (Четвертый этап, т.е. составление оптимального решения на основе полученной информации, рассматривается в упражнениях.) Структура кратчайшего пути Начнем с того, что охарактеризуем структуру оптимального решения. Для задачи о кратчайших путях между всеми парами вершин графа С = (К Е) доказано (лемма 24.1), что все частичные пути кратчайшего пути — тоже кратчайшие пути. Предположим, что граф представлен матрицей смежности И' = (ии).
Рассмотрим кратчайший путь р из вершины 1 в вершину з и предположим, что этот путь содержит не более гп ребер. Если циклы с отрицательным весом отсутствуют, то пз конечно. Если з = з, то вес пути р равен О, а ребра в нем отсутствуют. Если же вершины г и з различаются, то пуп р раскладывается на1- Й -+ у, где путь . р' р' содержит не более гп — 1 ребер. Согласно лемме 24.1, р' — кратчайший путь из вершины 1 в вершину к, поэтому выполняется равенство б (г, з) = б(1, 1с) + юь .
Часть ЧЕ Алгоритмы для работы с графами 712 Рекурсивное решение задачи о кратчайших путях между всеми парами вершин Пусть теперь 1, — минимальный вес любого пути из вершины г в вершину (т) )', содержащий не более т ребер. Если т = О, то кратчайший пугь из вершины ( в вершину ) существует тогда и только тогда, когда ( = )'. Таким образом, (о) (О если ( = ), (оо если г ~ у. Для т > 1 величина 1," вычисляется как минимум двух величин. Первая— (т) (вес кратчайшего нуги из вершины ( в вершину з, состоящего не более чем (тл — 1) из т — 1 ребер), а вторая — минимальный вес произвольного пути из вершины ( в вершину ), который состоит не более чем из т ребер. Этот минимальный вес получается в результате рассмотрения всех возможных предшественников /~ вершины з'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
