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