A. Суш;ествует цикл Ф~ отрицательного веса, для которого

Б. Не суш;ествует никакого цикла с отрицательным весом и

2 cfj>0 для всех циклов Ф. (X., xj)e<s>

B. Суш;ествует цикл с нулевым (но не отрицательным) весом, т. е.

2 Cij = 0 для некоторого цикла Ф .

(x, Xj)£O0

в случае А z* (минимальное значение z) меньше чем z*, так как неравенство

S 4- S Cjy-z S bj,<o

(X., ж^)бФ- (x, х^)еф- (X., ж^)еф-

может выполняться только при

(Xj. Х^)6Ф- (X., х^)6ф-

а это, очевидно, означает, что z* должно быть меньше чем z.

Аналогично в случае Б z* > а в случае В z* = z. Все сказанное приводит к следуюш;ей процедуре поиска. Начнем с некоторого значения г^. Если это значение слишком велико (т. е. имеет место случай А); возьмем <;z; если же оно слишком мало (т. е. имеет место случай Б), возьмем z > z-. Как только будут найдены верхняя и нижняя границы (соответственно г„ и Zj) для Z*, берем z** = (z + Zj)/2 и заменяем в случае А г„ на z**, а в случае Б - Zj на z**. Так как число итераций пропорционально числу значап1;их разрядов требуемой точности, т. е. пропорционально log I/t], где т] - величина погрешности, и так как каждая итерация (нахождение отрицательного цикла или вычисление полной матрицы расстояний) требует порядка операций, то решение сформулированной выше задачи с двойными весами требует О [п^ log i/r\] операций.

5. Нахождейие К кратчайших путей между двумя заданными вершинами

В разд. 2 были даны методы нахождения в произвольном графе кратчайшего пути от s к . Но во многих практических приложениях требуется еш;е, чтобы кратчайший путь обладал некоторыми

13 н. Кристофидес

дополнительными свойствами. Эту задачу можно, конечно, рассматривать как задачу кратчайшего пути с некоторыми дополнительными ограничениями [4] или как многоцелевую задачу, в которой учитываются не только длина пути, но и другие егО' свойства. Но эти усложнения будут, вообще говоря, сильно увеличивать вычислительную работу, и с практической точки зрения более просто найти К кратчайших путей от s к и выбрать среди них тот, который обладает нужными свойствами. Хотя такой метод и не эквивалентен прямому рассмотрению дополнительных свойств пути (пример этого будет дан в разд. 7 настоящей главы), но он применим даже в тех случаях, когда эти свойства сформулированы не строго или когда они по своей природе субъективны. В этом методе предполагается, что К кратчайших путей между s и t могут быть найдены достаточно эффективно. Именно это будет предметом изучения настоящей главы.

Мы будем здесь предполагать, что рассматриваются только-простые цепи. И хотя кратчайший путь необходимо должен быть простой цепью (при условии, что граф не содержит циклов отрицательного веса), но второй, третий и т. д. кратчайшие пути не обязаны быть такими даже в случае, когда все Сц положительны. Задача нахождения К кратчайших путей без требования, что они являются простыми цепями, намного проще, и для ее решения Хоффман и Пэвли [20], Сакарович [32], Беллман и Калаба [3J предложили итерационные методы, аналогичные описанным выше. Однако модифицирование этих методов с целью получения простых цепей осуществить не совсем легко, а так как почти во всех практических приложениях алгоритма нахождения К кратчайших путей требуются именно простые цепи, то мы опишем метод, предложенный Иеном [35] и позволяющий находить К кратчайших простых цепей.

Пусть = S, х\, . . ., ос, t - fc-й кратчайший путь от у к t, где а*, х\, . . ., х\ - соответственно 2-я, 3-я, . . ., q-a вершины й;-го кратчайшего пути. Пусть Р\ - отклонение от пути; Р^~ в точке ш. Под этим понимается следующее: Р\ - кратчайший из путей, совпадающих с Р\~ от s до г-й вершины, а затем идущий к вершине, отличной от (i 4- \)-х вершин тех (ранее уже-построенных) кратчайших путей (/ = 1, 2, . . ., А; - 1), которые имеют те же самые начальные подпути от s к г-й вершине, что и Р^~. Р\ приходит в вершину t по кратчайшему подпути, не проходящему ни через одну из вершин s, ж^ , . . ., участвующих в формировании первой части пути Р\. Отсюда следует, что путь pf необходимо должен быть простой цепью.

Первый подпуть s, з^, з^, . . ., х^ (совпадающий с s, х\~. xhi . . xf~) пути Pj называется его корнем и обознп-

чается R\, а второй подпуть xf, . . ., t пути называется ответвлением и обозначается через S}.

Алгоритм начинает работу с нахождения с помощью алгоритма кратчайшего пути от s к Z, описанного в разд. 2. Этот путь помещается в список (который должен содержать к-е кратчайшие пути). В общем случае для нахождения P нужно уже иметь кратчайшие пути Р^, Р^, . . ., Р'~. Ниже приводится описание алгоритма.

5.1. Описание алгоритма

Присвоение начальных значений

Шаг 1. Найти Р^. Положить к = 2. Если существует только один кратчайший путь Р^, включить его в список и перейти к шагу 2. Если таких путей несколько, но меньше, чем К, включить один из них в список Lc, а остальные в список L,. Перейти к шагу 2. Если существует К или более кратчайших путей р*, то задача решена. Останов.

Нахождение всех отклонений

Шаг 2. Найти все отклонения Pl (к - 1)-го кратчайшего пути Р^- для всех г == 1, 2, . . ., gu-i, выполняя для каждого i шаги с 3-го по 6-й.

Шаг 3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Р^~, с подпутем, образованным первыми j вершинами любого из путей Р' (/ = 1,2, . . к - 1). Если да, положить с {х\~, Xi+i) = схэ; в противном случае ничего не изменять. (При выполнении алгоритма вершина х^ обозначается s). Перейти к шагу 4.

Шаг 4. Используя алгоритм кратчайшего пути, найти кратчайшие пути от х\~ к t, исключая из рассмотрения вершины s, х\~, . . ., Хг . Если существует несколько кратчайших путей, взять в качестве S\ один из них.

Шаг 5. Построить Р\, соединеняя R\ {= s, х х ... . . X ~ с S и поместить Р в список L.

Шаг 6. Заменить элементы матрицы весов, измененные на шаге их первоначальными значениями и возвратиться к шагу 3.

Выбор кратчайших отклонений

Шаг 7. Найти кратчайший путь в списке Lj. Обозначить этот путь и переместить его из Li в Lq. Если к = К, то алгоритм