Глава 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, Кратчайшие пути

РИСУНОК 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. Алгоритмы на графах