Алгоритмы - построение и анализ (1021735), страница 135
Текст из файла (страница 135)
В примере, в котором рассматривается маршрут из Киева в Запорожье, карту дорог можно смоделировать в виде графа, вершины которого представляют перекрестки дорог„а ребра — отрезки дорог между перекрестками, причем вес каждого ребра равен расстоянию между соответствующими перекрестками. Цель — найти кратчайший путь от заданного перекрестка в Киеве (например, между улицамн Клавдиевской и Корсуньской) к заданному перекрестку в Запорожье (скажем, между улицами Панфиловцев и Патриотической). Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику.
Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму. Алгоритм поиска в ширину описанный в разделе 22.2, представляет собой алгоритм поиска кратчайшего пути по невзвешенному графу, т.е. по графу, каждому ребру которого приписывается единичный вес. Поскольку многие концепции, применяющиеся в алгоритме поиска в ширину, возникают при исследовании задачи о кратчайшем пути по взвешенным графам, рекомендуется освежить в памяти материал раздела 22.2. Варианты Настоящая глава посвящена задаче о кратчайшем пути из одной вершины (з(пд!е-зопгсе йопез!-рагпз ргоЫеш), в которой для заданного графа С = ()г, Е) требуется найти кратчайший путь, который начинается в определенной исходной вершине (зопгсе чег!ех) в Е Ъ' (для краткости будем именовать ее истоком) и заканчивается в каждой из вершин о е Ъ'.
Предназначенный для решения этой задачи алгоритм позволяет решить многие другие задачи, в том числе те, что перечислены ниже. ° Задача о кратчайшем пути в заданный пункт назначения (з1пя1е4езбпабоп з)зопез!-рабзз ргоЫегп). Требуется найти кратчайший пугь в заданную вершину назначения (безппа!юп чепех) 1, который начинается в каждой нз вершин о. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине. Глава 24.
Кратчайшие пути из одной вершины 665 ° Задача о кратчайшем пути между заданной парой вершин (з1пя!е-ра1г зЬопезыраг1зз ргоЫеш). Требуется найти кратчайший путь из заданной вершины и в заданную вершину и. Если решена задача о заданной исходной вершине и, то эта задача тоже решается. Более того, для этой задачи не найдено нн одного алгоритма, который бы в асимптотическом пределе был производительнее, чем лучшие из известных алгоритмов решения задачи об одной исходной вершине в наихудшем случае. ° Задача о кратчайшем пути между всеми парами вершин (а11-рава йопезь ра11зз ргоЫет).
Требуется найти кратчайший путь из каждой вершины и в каждую вершину ш Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее. Кроме того, структура этой задачи представляет интерес сама по себе. В главе 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),то вес путир' = (ео,пм...,о;,и;~.мо.ьз,...,иь) равен ю(р') = = ю (р) — ю (с) ( ю (р), так что р не может быть кратчайшим путем из вершины ео в вершину оы Остаются только циклы с нулевым весом.
Однако из пути можно удалить цикл с нулевым весом, в результате чего получится другой путь с тем же весом. Таким образом, если существует кратчайший путь из истока а в целевую вершину е, содержащий цикл с нулевым весом, то существует также другой кратчайший путь из истока в в целевую вершину о, в котором этот цикл не содержится. Если кратчайший путь содержит циклы с нулевым весом, эти циклы можно поочередно удалять до тех пор, пока не получим кратчайший путь, в котором циклы отсутствуют.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
