Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 21, Кратчайшие пути






Чтобы переназначить вес ребра, необходимо добавить к весу этого ребра разность
между весами начальной и конечной вершин ребра.

■ Чтобы переназначить вес сети, необходимо переназначить веса всех ребер сети.

Например, следующий простой код переназначает вес сети в соответствие с приняты­ми соглашениями:

for (v = 0; v < G->V(); v++)

{ typename Graph::adjIterator A(G, v); for (Edge* e = A.beg(); !A.end() ; e = A.nxt())

e->wt() s e->wt() + wt[v] - wt[e->w()] }

Эта операция является простым линейным во времени процессом, который строго определен для всех сетей, независимо от весов. Замечательно, что кратчайшие пути в по­лученной сети остаются теми же, что и кратчайшие пути в исходной сети.

Свойство 21.23. Переназначение весов сети не воздействует на кратчайшие пути.

Доказательство: Для любых двух заданных вершин s и t переназначение весов изменя­ет вес любого пути из s в t за счет добавления разности между весами s и t Это утвер­ждение легко доказать методом индукции по длине пути. При переназначении веса сети вес каждого пути из s в t изменяется на одно и то же значение каким бы путь ни был, длинным или коротким. В частности, этот факт предполагает непосредственно, что длина кратчайшего пути между любыми двумя вершинами в преобразованной сети остается такой же, как и длина кратчайшего пути между ними в исходной сети. ■

Поскольку в путях между различными парами вершин веса могут быть переназначе­ны по-разному, переназначение весов могло бы повлиять на такие факторы, которые включают сравнение длин кратчайших путей (например, вычисление диаметра сети). В таких случаях нам следует обратить переназначение весов после завершения вычисления кратчайших путей, но перед использованием результатов.

Переназначение весов не помогает в случае сетей с отрицательными циклами: эта опе­рация не изменяет веса ни одного цикла, так что с ее помощью мы не можем удалить от­рицательные циклы. Но для сетей без отрицательных циклов мы можем стремиться об­наружить такое множество вершин, что переназначение весов приведет к весам ребер, которые являются неотрицательными, независимо от того, каковы были первоначальные веса. С неотрицательными весами ребер мы можем затем решить задачу поиска кратчай­ших путей для всех пар с помощью версии алгоритма Дейкстры для всех пар. Например, рис. 21.31 дает такой пример для нашей типовой сети, а рис. 21.32 показывает вычисле­ние кратчайших путей по алгоритму Дейкстры на преобразованной сети без отрицатель­ных ребер. Следующее свойство показывает, что мы всегда можем найти такое множе­ство весов.



Свойство 21.24. В произвольной сети, не содержащей отрицательных циклов, выберем про­извольную вершину s и присвоим каждой вершине \ вес, равный длине кратчайшего пути в v из s. Переназначение весов сети с этими весами вершин дает в результате неотрицатель­ные веса ребер для каждого ребра, которое соединяет вершины, достижимые из s.

Доказательство: Для заданного произвольного ребра v-w вес v суть длина кратчайше­го пути в v, а вес w суть длина кратчайшего пути в w. Если v-w есть конечное ребро



Часть 5.Алгоритмы на графах


 


на кратчайшем пути в w, то разность между весом w и весом v в точности составит вес v-w. Другими словами, переназначение веса ребра даст вес 0. Если кратчайший путь через w не проходит через v, то вес v плюс вес v-w должен быть больше или ра­вен весу w. Другими словами, переназначение веса ребра даст положительный вес. ■

Подобно тому, как это было в случае применения алгоритма Беллмана-Форда для обнаружения отрица­тельных циклов, существуют два способа, чтобы в про­извольной сети без отрицательных циклов сделать вес каждого ребра неотрицательным. Либо можно начать с источника в каждой сильно связной компоненте, либо добавить к каждой вершине сети фиктивную вер­шину с ребром длины 0. В любом случае результатом будет остовный лес кратчайших путей, которым мож­но воспользоваться для присвоения весов вершинам (а именно, веса пути в SPT из корня в вершину).

Например, значения весов, выбираемые на рис. 21.31, являются в точности длинами кратчайших путей из 4, поэтому ребра в дереве кратчайших путей с кор­нем в 4 имеют веса 0 для сети с переназначенными ве­сами.



В конечном итоге мы можем решить задачу поис­ка кратчайших путей для всех пар в сетях, которые со­держат отрицательные веса ребер, но не имеют отри­цательных циклов, продолжая следующим образом:

■ При помощи алгоритма Беллмана-Форда нахо­
дим лес кратчайших путей в исходной сети.

■ Если алгоритм выявляет отрицательный цикл,
сообщаем об этом факте и завершаем работу.

■ Переназначаем вес сети на основе леса.

■ Применяем версию алгоритма Дейкстры для
всех пар к сети с переназначенными весами.

После этих вычислений матрица путей дает крат­чайшие пути в обеих сетях, а матрица расстояний дает длины путей в сети с переназначенными весами. Эта последовательность шагов иногда известна как алго­ритм Джонсона (Johnson's algorithm) (см. раздел ссылок).


РИСУНОК 21.31. ПЕРЕНАЗНАЧЕНИЕ ВЕСОВ СЕТИ

Для любого произвольно заданного распределения весов на вершинах (верхняя часть рисунка) можно переназначить веса всех ребер в сети за счет добавления к каждому весу ребра, разности весов его начальной и конечной вершин. Переназначение весов не воздей­ствует на кратчайшие пути, поскольку оно вносит одно и то же изменение в веса всех путей, соединяющих каждую пару вершин. Например, рассмотрим путь 0-5-4-2-3, его вес в первоначальной сети есть 0.29 + 0.21 + 0.32 + 0.50 = 1.32, а в переназначенной сети — 1.12 + 0.19 + 0.12 + 0.34 = 1.77; эти веса отличаются на 0.45 = 0.81 — 0.36, т.е. на разность весов вершин 0 и 3. При этом веса всех путей между 0 и 3 изменились на одну и ту же величину.


Свойство 21.25. С помощью алгоритма Джонсона можно решить задачу поиска кратчай­ших путей для всех пар в сетях, которые не содержат отрицательных циклов, за время, пропорциональное VE log(d)V где d = 2, если Е < 2V, и d = E/V в противном случае.


Глава 21, Кратчайшие пути




РИСУНОК 21.32. ВСЕ КРАТЧАЙШИЕ ПУТИ В СЕТИ С ПЕРЕНАЗНАЧЕННЫМИ ВЕСАМИ

Эти диаграммы показывают SPT для каждой вершины в сети, обратной для сети с переназначенными весами из рис. 21.31, которые были бы получены по алгоритму Дейкстры при вычислении кратчайших путей в исходной сети из рис. 21.26. Эти пути являются такими же, как для сети перед переназначением весов (см. рис. 21.9). Векторы st в этих схемах представляют собой столбцы матрицы путей из рис. 21.26. Векторы wt в этой схеме соответствуют столбцам в матрице расстояний, но нам необхо­димо отменить переназначе­ние весов для каждого элемента за счет вычитания веса исходной вершины и добавления веса конечной вершины в пути (см. рис. 21.31). Например, из третьей строки снизу можно видеть, что в обоих сетях кратчайшим путем из 0 в 3 будет 0-5-1-4-3,а его длина составляет 1.13в показан­ной здесь сети с переназна­ченными весами. Сравнивая с рис. 21.31 можно вычислить его длину в исходной сети, вычтя вес 0 и добавив вес 3, получив при этом результат 1.13-0.81 + 0.36 = 0.68,т.е. элемент в строке 0 и столбце 3 матрицы расстоя­ний на рис. 21.26. Все кратчайшие пути, ведущие в 4 в этой сети, имеют длину 0, поскольку эти пути использовались для переназ­начения весов.



Часть 5. Алгоритмы на графах


Доказательство: См. свойства 21.22-21.24 и резюме, подведенное в предыдущем абза­це. Граница худшего случая времени выполнения непосредственно вытекает из свойств 21.7 и 21.22. ■

Для реализации алгоритма Джонсона мы объединяем реализацию программы 21.9, код переназначения весов, рассмотренный перед свойством 21.23, и реализацию алгоритма Дейкстры поиска кратчайших путей для всех пар из программы 21.4 (или из программы 20.6 для случая плотных графов). Как отмечалось в доказательстве свойства 21.22, мы дол­жны соответствующим образом модифицировать алгоритм Беллмана-Форда для сетей, которые не являются сильно связными (см. упражнения 21.135—21.137). Для завершения реализации интерфейса поиска кратчайших путей для всех пар можно либо вычислить истинные длины путей за счет вычитания веса начальной и добавления веса конечной вер­шины (т.е. отменить операцию переназначения весов для путей) при копировании двух векторов в матрицы расстояний и путей в алгоритме Дейкстры, либо поместить эти вы­числения в GRAPHdistв реализации АТД.

Для сетей, не содержащих отрицательных весов, задача выявления циклов решается более просто, чем задача вычисления кратчайших путей из единственного источника ко всем другим вершинам; при этом последняя решается более просто, чем задача вычисле­ния кратчайших путей, соединяющих все пары вершин. Данные факты соответствуют на­шим интуитивным представлениям. В противоположность этому, аналогичные факты для сетей, которые содержат отрицательные веса, нам кажутся противоестественными: алго­ритмы, которые мы обсудили в этом разделе, показывают, что для сетей, которые содер­жат отрицательные веса, лучшие из известных алгоритмы решения трех упомянутых за­дач обладают сходными характеристиками быстродействия для худшего случая. Например, в худшем случае, определение, содержит ли сеть единственный отрицательный цикл, при­близительно столь же сложно, как и поиск всех кратчайших путей в сети того же разме­ра, которая не имеет отрицательных циклов.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.014 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал