Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 137
Текст из файла (страница 137)
Кроме того, структура этой задачи представляет интерес сама по себе. В главе 25 задача обо всех парах вершин исследуется более подробно. Оптимальная структура задачи о кратчайшем пути Алгоритмы поиска кратчайших путей обычно основаны на том свойстве, что кратчайший путь между двумя вершинами содержит в себе другие кратчайшие пути. (В основе описанного в главе 26 алгоритма Эдмондса-Карпа (ЕйпопсЬ-Ка~р), предназначенного для поиска максимального потока, также лежит это свойство). Это свойство оптимальной структуры — критерий применимости и динамического программирования (глава 15), и жадного метода (глава 16).
Алгоритм Дейкстры (Р1)кэпа), с которым мы ознакомимся в разделе 24.3, представляет собой жадный алгоритм, а алгоритм Флойда-Воршалла (Р1оуд-%агзпаИ), предназначенный для поиска кратчайшего пути между всеми парами вершин (см. главу 25), — это алгоритм динамического программирования. В сформулированной ниже лемме данное свойство оптимальной структуры определяется точнее. Лемма 24.1 (Частичные пути кратчайшего пути являются кратчайшими путями.) Пусть р = (щ, сз,..., сь) — кратчайший путь из вершины щ к вершине сь в заданном взвешенном ориентированном графе С = (р", Е) с весовой функцией и: Š— К, а ру — — (пи с;+ы..., сз) — частичный путь пути р, который проходит из вершины кл к вершине и для произвольных ( и з, удовлетворяющих неравенству 1 < ( < з < )с. Тогда р, — кратчайший путь из вершины с; к вершине с .
Рн Рз Р~и Доказательство. Если разложить путь р на составные части щ -4 кз -* с - пь, то будет выполняться соотношение и (р) = ю (ри) + ш (р,у) + ю (р я). Теперь предположим, что существует путь р'; из вершины кч к вершине пэ, вес которого / ян Р*. пч удовлетворяет неравенству и(р; ) < ы(р, ) Тогда с1 - кз -» с - сь — путь Часть Ч!. Алгоритмы для работы с графами 666 из вершины о1 к вершине оы вес которого ю(рп) + ю (р'; ) + ю(р ь) меньше веса ю (р). Это противоречит предположению о том, что р — кратчайший путь из вершины е1 к вершине еь.
Ребра с отрицательным весом В некоторых экземплярах задачи о кратчайшем пути из фиксированного истока, веса ребер могут принимать отрицательные значения. Если граф С = Я Е) не содержит циклов с отрицательным весом, достижимых из истока з, то вес кратчайшего пути б (з, о) остается вполне определенной величиной для каждой вершины о е У, даже если он принимает отрицательное значение. Если же такой цикл достижим из истока з, веса кратчайших путей перестают быть вполне определенными величинами. В этой ситуации ни один путь из истока з в любую из вершин цикла не может быть кратчайшим, потому что всегда можно найти путь с меньшим весом, который проходит по предложенному "кратчайшему" пути, а потом обходит цикл с отрицательным весом.
Если на некотором пути из вершины з к вершине о встречается цикл с отрицательным весом, мы определяем б(з,о) = -оо. На рис. 24.1 проиллюстрировано влияние наличия отрицательных весов и циклов с отрицательным весом на веса кратчайших путей. Поскольку из вершины з в вершину а ведет всего один путь (путь (з,а)), то выполняется равенство б (з, а) = ю (з, а) = 3. Аналогично, имеется всего один путь из вершины з в вершину Ь, поэтому б (з, Ь) = ю (з, а) + ю (а, Ь) = 3+ (-4) = — 1.
Из вершины з в вершину с можно провести бесконечно большое количество путей: (з, с), (з, с, г1, с), (з, с, Ы, с, Н, с) и т.д. Поскольку вес цикла (с, И, с) равен 6+ ( — 3) = 3 ) О, т.е. он положительный, кратчайший путь из вершины з в вершину с — это (з, с) вес которого равен б (з, с) = 5. Аналогично, кратчайший путь из вершины з в вершину б — (з, с, Щ, с весом б(з, Н) = ю(з,с) + ю(с, Н) = 11. Существует бесконечно большое количество путей из з в вершину е: (з,е), (з,е, !',е), (з,е,г",е,г",е) ит.д. Однако поскольку вес цикла (е, 1, е) равен 3 + ( — 6) = — 3 < О, т.е.
он отрицательный, не существует кратчайшего пути из вершины з в вершину е. Обходя цикл с отрицательным весом (е, Г", е) сколько угодно раз, можно построить путь из з в вершину е, вес которого будет выражаться как угодно большим по модулю отрицательным числом, поэтому б (з, е) = -оо; аналогично, б (з, г") = — оо. Поскольку вершина д достижима из вершины г, можно также найти пути из вершины з в вершину д с произвольно большими отрицательными весами, поэтому б (з, д) = — оо. Вершины 6, г и д также образуют цикл с отрицательным весом. Однако они недостижимы из вершины з, поэтому б (з, й) = б (з, г) = б (з, у) = оо. В некоторых алгоритмах поиска кратчайшего пути, таких как алгоритм Дейкстры, предполагается, что вес любого из ребер входного графа неотрицательный, как это было в примере о дорожной карте.
В других алгоритмах, таких как алго- Глава 24. Кратчайшие пути иэ одной вершины 667 Г ., л Рис. 24.1. Ребра с отрицательным весом в ориентированном графе. В каждой вершине обозначен вес кратчайшего пути в эту вершину из вершины а ритм Беллмана-Форда (Ве!1шап-Роп1), ребра входных графов могут иметь отрицательный вес. Эти алгоритмы дают корректный ответ, если циклы с отрицательным весом недостижимы из истока. Обычно, если такой цикл с отрицательным весом существует, подобный алгоритм способен выявить его наличие и сообщить об этом.
Циклы Может ли кратчайший путь содержать цикл? Только что мы убедились, что он не может содержать цикл с отрицательным весом. В него также не может входить цикл с положительным весом, поскольку в результате удаления этого цикла из пути получится путь, который исходит из того же истока и оканчивается в той же вершине, но обладает меньшим весом. Таким образом, если р = (оо, оы..., иь)— путь, а с = (о,, е;~м..., оу) — цикл с положительным весом на этом пути (те.
ог = = е ию(с) ) 0),то вес путир' = (ео,пм...,о;,и;~.мо.ьз,...,иь) равен ю(р') = = ю (р) — ю (с) ( ю (р), так что р не может быть кратчайшим путем из вершины ео в вершину оы Остаются только циклы с нулевым весом. Однако из пути можно удалить цикл с нулевым весом, в результате чего получится другой путь с тем же весом. Таким образом, если существует кратчайший путь из истока а в целевую вершину е, содержащий цикл с нулевым весом, то существует также другой кратчайший путь из истока в в целевую вершину о, в котором этот цикл не содержится. Если кратчайший путь содержит циклы с нулевым весом, эти циклы можно поочередно удалять до тех пор, пока не получим кратчайший путь, в котором циклы отсутствуют.
Поэтому без потери общности можно предположить, что если ведется поиск кратчайших путей, они не содержат циклов. Поскольку в любой ациклический путь в графе С = (1г, Е) входит не более 11г1 различных вершин, в нем Часть Ч!. Алгоритмы для работы с графами 668 также содержится не более [Ц вЂ” 1 ребер. Таким образом, можно ограничиться рассмотрением кратчайших путей, состоящих не более чем из [Ц вЂ” 1 ребер. Представление кратчайших путей Часто требуется вычислить не только вес каждого из кратчайших путей, но и входящие в их состав вершины. Представление, которое используется для кратчайших путей, аналогично тому, что используется для описанных в разделе 22.2 деревьев поиска в ширину.
В заданном графе С = (Ъ; Е) для каждой вершины с б У поддерживается атрибут яредшественпшг (ргедесеззог) я [е[, в роли которого выступает либо другая вершина, либо значение ьпь. В рассмотренных в этой главе алгоритмах поиска кратчайших пугей атрибуты 1г присваиваются таким образом, что цепочка предшественников, которая начинается в вершине е, позволяет проследить путь, обратный кратчайшему пути из вершины а в вершину о. Таким образом, для заданной вершины с, для которой я [е! ф мп., с помощью описанной в разделе 22.2 процедуры Ркпчт Рлтн(С, а, с) можно вывести кратчайший путь из вершины а в вершину с. Однако до тех пор, пока алгоритм поиска кратчайших путей не закончил свою работу, значения я не обязательно указывают кратчайшие пути. Как и при поиске в ширину, нас будет интересовать подграф предшесягвоваиия (ргедесеззог апЬйгарЬ) С = (Ъ', Е ), построенный на основании значений я.
Как и раньше, определим множество вершин К, как множество, состоящее из тех вершин графа С, предшественниками которых не являются значения нп., а также включает исток ьч 1г„= [с Е У: ~г [с[ ~ Х!%.) 0 [а) . Множество ориентированных ребер Š— это множество ребер, индуцированных значениями гг вершин из множества У„: Е„= ((я [с], с) Е Е: е Е У' — (аЦ . Далее будет доказано, что значения я, полученные с помощью описанных в этой главе алгоритмов, обладают тем свойством, что после завершения этих алгоритмов С является "деревом кратчайших путей".
Неформально это дерево можно описать как корневое дерево, содержащее кратчайший путь из истока э к каждой вершине, достижимой из вершины ж Оно похоже на дерево поиска в ширину, знакомое нам по разделу 22.2, но содержит кратчайшие пути из истока, определенные не с помощью количества ребер, а с помощью значений их весов. Дадим более точное определение. Пусть С = (Ъ", Е) — взвешенный ориентированный граф с весовой функцией ю: Е -+ К. Предположим, что в нем не содержится циклов с отрицательным весом, достижимых из истока а Е Ъ', а следовательно, Часть Ч1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
