Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 138
Текст из файла (страница 138)
Алгоритмы для работы с графами 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!шап-Рогд а!копани) позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным.
Для заданного взвешенного ориентированного графа С = (Ъ", Е) с истоком а и весовой функцией и: Š— К алгоритм Белл- мана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует.
Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес. В этом алгоритме используется ослабление, в результате которого величина 0 1с], представляющая собой оценку веса кратчайшего пути из истока а к каждой из вершин е Е Ъ', уменьшается до тех пор, пока она не станет равна фактичесюму весу кратчайшего пути б (з, е). Значение ткт!к возвращается алгоритмом Глава 24. Кратчайшие пути из одной вершины 673 и Рнс.
24.4. Выполнение алгоритма Беллмаиа-Форда тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока. Веы.мАтч РОк0(С, ш, з) 1 1ьлт!АМЕБ Бпчпье БООксе(С, 3) 2 аког г' - 1 Го [У[С)[ — 1 3 бо аког (для) каждого ребра (и, о) Е Е[С] 4 бо ВЕЬАХ(и, о, и) 5 аког (для) каждого ребра (и, и) Е Е[С) б йо Ыг1[й> 0[и]+ш(и,и) 7 тпеп гетпгп РАьзе 8 гетнгп ВШЕ На рис.
24.4 проиллюстрирована работа алгоритма Веь МАм Ропп с графом, содержащим 5 вершин, в котором исток находится в вершине а. Рассмотрим, как работает алгоритм. После инициализации в строке 1 всех значений Н и я, алгоритм осуществляет [Ц вЂ” 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла Рог в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После [Ц вЂ” 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответствующее булево значение.
(Причины, по которым эта проверка корректно работает, стануг понятными несколько позже.) В примере, приведенном на рис. 24.4, алгоритм Беллман-Форд возвращает значение тКОЕ. Часть Ч!. Алгоритмы для работы с графами 674 На рис. 24.4 в вершинах графа показаны значения атрибутов Н на каждом этапе работы алгоритма, а выделенные ребра указывают на значения предшественников: если ребро (и, о) выделено, то я [о] = и. В рассматриваемом примере при каждом проходе ребра ослабляются в следующем порядке: (1, х), (1, у), (г, г), (х,1), (у,х), (у, в), (х, х), (в, в), (в, г), (в,у). В части а рисунка показана ситуация, сложившаяся непосредственно перед первым проходом по ребрам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
