Алгоритмы - построение и анализ (1021735), страница 136
Текст из файла (страница 136)
Поэтому без потери общности можно предположить, что если ведется поиск кратчайших путей, они не содержат циклов. Поскольку в любой ациклический путь в графе С = (1г, Е) входит не более 11г1 различных вершин, в нем Часть Ч!. Алгоритмы для работы с графами 668 также содержится не более [Ц вЂ” 1 ребер. Таким образом, можно ограничиться рассмотрением кратчайших путей, состоящих не более чем из [Ц вЂ” 1 ребер.
Представление кратчайших путей Часто требуется вычислить не только вес каждого из кратчайших путей, но и входящие в их состав вершины. Представление, которое используется для кратчайших путей, аналогично тому, что используется для описанных в разделе 22.2 деревьев поиска в ширину. В заданном графе С = (Ъ; Е) для каждой вершины с б У поддерживается атрибут предшественник (ргедесеззог) я [е[, в роли которого выступает либо другая вершина, либо значение ьпь. В рассмотренных в этой главе алгоритмах поиска кратчайших пугей атрибуты 1г присваиваются таким образом, что цепочка предшественников, которая начинается в вершине е, позволяет проследить путь, обратный кратчайшему пути из вершины а в вершину о. Таким образом, для заданной вершины с, для которой я [е! ф мп., с помощью описанной в разделе 22.2 процедуры Ркпчт Рлтн(С, а, с) можно вывести кратчайший путь из вершины а в вершину с.
Однако до тех пор, пока алгоритм поиска кратчайших путей не закончил свою работу, значения я не обязательно указывают кратчайшие пути. Как и при поиске в ширину, нас будет интересовать подграф предшесягвоваиия (ргедесеззог апЬйгарЬ) С = (Ъ', Е ), построенный на основании значений я. Как и раньше, определим множество вершин К, как множество, состоящее из тех вершин графа С, предшественниками которых не являются значения нп., а также включает исток ьч 1г„= [с Е У: ~г [с[ ~ Х!%.) 0 [а) .
Множество ориентированных ребер Š— это множество ребер, индуцированных значениями гг вершин из множества У„: Е„= ((я [с], с) Е Е: е Е У' — (аЦ . Далее будет доказано, что значения я, полученные с помощью описанных в этой главе алгоритмов, обладают тем свойством, что после завершения этих алгоритмов С является "деревом кратчайших путей". Неформально это дерево можно описать как корневое дерево, содержащее кратчайший путь из истока э к каждой вершине, достижимой из вершины ж Оно похоже на дерево поиска в ширину, знакомое нам по разделу 22.2, но содержит кратчайшие пути из истока, определенные не с помощью количества ребер, а с помощью значений их весов.
Дадим более точное определение. Пусть С = (Ъ", Е) — взвешенный ориентированный граф с весовой функцией ю: Е -+ К. Предположим, что в нем не содержится циклов с отрицательным весом, достижимых из истока а Е Ъ', а следовательно, Часть Ч1. Алгоритмы для работы с графами 670 , 'князю,»;ч У' з з г- — "— -ъ К ь ! л ч! и, Г, ь ) Рис. 24З. Ослабление ребра (и, о) с весом и (и, и) = 2 Процесс ослабления' (ге!ахайоп) ребра (и, и) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине и, проведя его через вершину и, а также в обновлении атрибутов г1 [и] и и [и] при наличии такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути г1 [и] и обновить поле зг [и] вершины и.
Приведенный ниже код выполняет ослабление ребра (и,и): Кб~.ЛХ(и, и, ю) 1 11 с[[и] > с[[и] + ю(иг и) 2 Феп г1[и] — г1[и] + ю(и, и) 3 зг[и] — и На рис. 24.3 приведены два примера ослабления ребра; в одном из этих примеров оценка кратчайшего пути понижается, а в другом — не происходит никаких изменений, связанных с оценками. В каждой вершине на рисунке приводится оценка кратчайшего пути к этой вершине.
В примере, приведенном в части а рисунка, перед ослаблением выполняется неравенство г( [и] > с1 [и] + ю (и, и), поэтому в результате ослабления значение г1 [и] уменьшается. В части б рисунка перед ослаблением выполняется неравенство д [и] < г1 [и] + ю (и, и), поэтому значение г[ [и] остается неизменным. В каждом из описанных в этой главе алгоритмов сначала вызывается процедура 1ьлтглшж Я|наьв Боггксе, а затем производится ослабление ребер. Более того, ослабление — единственная операция, изменяющая оценки кратчайших путей и предшественников. Описанные в этой главе алгоритмы различаются тем, сколько раз в них производится ослабление ребер, а также порядком ребер, над которыми выполняется ослабление.
В алгоритме Дейкстры и алгоритме поиска кратчайших путей в ориентированных ациклических графах каждое ребра Может показаться странным, что термин "ослабление" используется для операции, которая уточняет верхнюю границу. Этот термин определился исторически. Результат этапа ослабления можно рассматривать как ослабление ограничения И [и] < гз [и) + ю (и, и), которое лолжио выполняться согласно неравенству треугольника (лемма 24.10), если И[и) = б(а,п) и И[о[ = б(а,с). Другими словами, если справедливо неравенство 4[о[ < И[и[+ зс(п,с), оно выполняется без "давления", поэтому данное условие "ослабляется". Глава 24.
Кратчайшие пути из одной вершины 671 ослабляется ровно по одному разу. В алгоритме Беллмена-Форда (ВеПшап-Рогд) каждое ребро ослабляется по несколько раз. Свойства кратчайших путей и ослабления Для доказательства корректности описанных в этой главе алгоритмов будут использоваться некоторые свойства кратчайших путей и ослабления. Здесь эти свойства лишь сформулированы, а в разделе 24.5 будет представлено их формальное доказательство. Чтобы не нарушалась целостность изложения, каждое приведенное здесь свойство содержит номер соответствующей ему леммы или следствия из раздела 24.5. В последних пяти свойствах, которые относятся к оценкам кратчайших путей или подграфу предшествования, подразумевается, что они инициализированы с помощью вызова процедуры 1мтишге Бпчоье Бо11ксе(С, а), и что единственный способ, используемый для изменения оценок кратчайших путей и подграфа предшествования, — выполнение некоторой последовательности этапов ослабления.
Неравенство треугольника (лемма 24.10). Для каждого ребра (и, и) Е Е выполняется неравенство б (а, о) < б (а, и) + + ш(и,о). Свойство верхней границы (лемма 24.11). Для всех вершин и Е У всегда выполняется неравенство И[и] > б(з,и), а после того, как величина Н [и] становится равной б (а, и), она больше не изменяется. Свойство отсутствия пути (следствие 24.12). Если из вершины а в вершину и нет пути, то всегда выполняется соотношение о'[и] = б(о,и) = оо. Свойство сходимости (лемма 24.14). Если а - и — и — кратчайший в графе С путь для некоторых вершин и, и Е У, и если равенство д [и] = б (а, и) выполняется в некоторый момент времени до ослабления ребра (и, и), то в любой момент времени после этого И[и] = б(а,и). Свойство ослабления пути (лемма 24.15).
Если р = (ио,ом...,оь) — кратчайший путь из вершины а = оо в вершину о „и ослабление ребер пути р производится в порядке (ио, о1), (иы из)„..., (оа моя), то о[иь] = б(а,ия). Это свойство выполняется независимо от других этапов ослабления, даже если они чередуются с ослаблением ребер, принадлежащих пути р. Свойство подграфа предшествования (лемма 24.17).
Если для всех вершин о Е У выполняется равенство с( [и] = б (а, и), то подграф предшествования представляет собой дерево кратчайших путей с корнем в истоке а Часть Ч!. Алгоритмы для работы с графами 672 Краткое содержание главы В разделе 24.1 представлен алгоритм Беллмана-Форда, позволяющий решить задачу о кратчайшем пути из фиксированного истока в общем случае, югда вес любого ребра может быть отрицательным.
Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. В разделе 24.2 приводится алгоритм с линейным временем выполнения, предназначенный для построения кратчайших путей из одной вершины в ориентированном ациклическом графе. В разделе 24.3 описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Беллмана-Форда„ио требует, чтобы вес каждого из ребер был неотрицательным. В разделе 24.4 показано, как с помощью алгоритма Беллмана-Форда можно решить частный случай задачи линейного программирования.
Наконец, в разделе 24.5 доказываются сформулированные выше свойства кратчайших путей и ослабления. Примем некоторые соглашения, необходимые для выполнения арифметических операций с бесконечно большими величинами. Будем считать, что для любого действительного числа а ф — оо выполняется соотношение а + оо = оо + + а = оо. Кроме того, чтобы наши доказательства сохраняли силу при наличии циклов с отрицательным весом, будем считать, что для любого действительного числа а ф оо выполняется соотношение а + ( — оо) = (-оо) + а = -оо.
Во всех описанных в этой главе алгоритмах предполагается, что ориентированный граф С хранится в виде списков смежных вершин. Кроме того, вместе с каждым ребром хранится его вес, так что при просмотре каждого списка смежности вес каждого нз его ребер можно определить в течение времени О (1). 24.1 Алгоритм Беллмана-Форда Алгориам Беллмана-Форда (Ве1!шап-Рогд а!копани) позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным.
Для заданного взвешенного ориентированного графа С = (Ъ", Е) с истоком а и весовой функцией и: Š— К алгоритм Белл- мана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
