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