(б) Если все о и А; = п, то получено решение. Матрица [cij] дает длины всех кратчайших путей. Останов.

(в) Если все Сц 0, но А; <; п, то вернуться к шагу 2. Доказательство оптимальности ответа, полученного с помощью

Этого алгоритма, чрезвычайно простое [21], [27], и мы предоставляем его читателю. Основная операция алгоритма, определяемая соотношением (8.5), называется трехместной операцией. Она имеет разнообразные применения в задачах той же природы, что и задача о кратчайшем пути. Такие задачи обсуждаются в последующих разделах.

Сами кратчайшие пути можно найти по их длинам с помощью рекурсивной процедуры, подобной той, которая выше определялась соотношением (8.2). С другой стороны, можно использовать технику, предложенную Ху [21], для записи информации о самих путях (наряду с информацией о длинах путей). Этот последний метод аналогичен использованному в разд. 2.2.1 и особенно полезен в тех случаях, когда требуется найти в графе цикл отрицательного веса (если такой существует). В этом методе в дополнение к матрице весов С хранится и обновляется вторая (п X п)-матрица в = [6jj-]. Элемент указывает вершину, непосредственно предшествующую вершине Xj в кратчайшем пути от Xt к Xj. Матрице в присваиваются начальные значения 0; = Xi для всех Х; и xj.

В соответствии с (8.5) на шаге 3 алгоритма обновление матрицы происходит так:

{0ft,j-, если {cth + Ckj)<.Cij в квадратных скобках в выражении (8.5), не изменяется, если Cij{cif,-\-Ckj).

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

Xi, Ху . . ., Ху, Х^, Ха Xj,

где Ха = Qij, Xg = 0га, Xv = 0гв и т. д. до Xi = Qi.

Здесь следует отметить, что если всем Сц придать начальные значения оо (а не 0), то конечное значение величины Сц будет равно весу цепи, проходящей через вершину xi. Легко также видеть, что, исходя из структуры матрицы в, полученной в процессе той итерации, когда элемент Сц становится отрицательным, легко найти цикл отрицательного веса, соответствующий этому элементу.

Это обстоятельство используется в гл. 11 при реализации основного шага в алгоритме- поиска в графе потока минимальной Стоимости. Оно оказывается также полезным и во многих других приложениях (об этом говорится в следующем разделе).

4. Обнаружение циклов отрицательного веса

Задача выявления циклов отрицательного веса в произвольном графе вашна как сама по себе, так и в качестве основного шага в более сложных алгоритмах (см. разд. 4.1 ниже и гл. И). В настоящем разделе эта задача обсуждается несколько более подробно, чем в предыдущем.

В разд. 3.1 отмечалось, что алгоритм Флойда нахождения кратчайших путей между всеми парами вершин может быть использован и для обнаружения в графе циклов отрицательного веса. Кроме того, в тех случаях, когда в графе имеется вершина из которой достижимы все остальные вершины этого графа, для нахождения циклов отрицательного веса можно также использовать алгоритм из разд. 2.2.1 (как это указывается на шаге 3(в)). Если не все вершины графа G достижимы из s (например, когда G является неориентированным графом, составленным не менее чем из двух связных компонент), то алгоритм разд. 2.2.1 завершит работу (как и должно быть) при следующем распределении пометок: у вершин из компоненты, содержащей s, пометки конечные, а пометки вершин в других компонентах равны сю. В этом случае циклы отрицательного веса, лежащие в других компонентах, не будут обнаружены. Тем не менее во многих важных приложениях алгоритма обнаружения цикла отрицательного веса (см., например, гл. И, разд. 5) всегда имеется в распоряжении вершина S, из которой достижимы все остальные вершины. В таких случаях алгоритм из разд. 2.2.1 при поиске циклов отрицательного веса предпочтительней с вычислительной точки зрения, чем алгоритм Флойда.

Правила остановки алгоритма из разд. 2.2.1 даются в форме, позволяющей минимизировать объем вычислений при поиске кратчайших путей из вершины s, если только в графе G отсутствуют циклы отрицательного веса. Эти правила могут быть видоизменены так, чтобы циклы отрицательного веса обнаруживались по возможности быстрее.

После каждого изменения пометки вершины Xj и нахождения подходящей вершины xj*, удовлетворяющей соотношению (8.3), можно проверить, действительно ли х^ принадлежит текущему кратчайшему пути от s к xj* (этот путь можно найти, используя текущие пометки 6). Если это так, то вершина Xj* была помечена через Xj и из неравенства (xj*) -Ь с (xj*, xi) <С Z* (xj) следует, что часть текущего кратчайшего пути от х,- к Xj* вместе с дугой {xj*, Xj) должна образовывать цикл отрицательного веса и работа алгоритма может закончиться. Если же пометка вершины Xj либо не изменяется (в соответствии с (8.3)), либо изменяется, но Xf не будет принадлежать текущему кратчайшему пути от s к Xj.,

минимальна (или максимальна).

Рассмотрим, например, обслуживание судном или самолетом некоторой сети маршрутов и предположим, что - выгода , а bij - время , необходимое для прохождения по дуге (х^, х/). Задача нахождения замкнутого обслуживаемого маршрута максимизирующего выгоду, относится к задачам описываемого типа. Более реалистичные задачи, учитывающие емкость транспортных средств ИТ. д., рассмотрены в работе [9].

Другими задачами, которые можно сформулировать как задачи нахождения оптимальных циклов в графах с двойными весами, являются задачи планирования параллельных вычислений [31] и управления технологическими процессами [6].

Задачу нахождения в графе с двойными весами цикла Ф, для которого отношение z* (Ф) минимально, можно решить, используя алгоритм обнаружения в графе цикла отрицательного веса. Это делается так. Допустим, что веса с, и btj - произвольные действительные числа (положительные, отрицательные или нуль) с единственным ограничением, что для всех циклов Ф из G

S bij > 0. {В большинстве практических ситуаций, напри-

мер, упомянутых выше, Cjy О, но bij >. О для всех i и /.)

Возьмем некоторое пробное значение z* целевой функции Z (Ф) и рассмотрим граф G с модифицированными весами

Ci} = cij-bij.

Попытка найти в G цикл отрицательного веса с матрицей [cij] может привести к следующим трем возможностям.

то работа алгоритма может продолжаться до шага 3(a). Следует заметить, что описанная модификация делает излишним шаг 3(в) алгоритма ие разд. 2.2.1, так как теперь цикл отрицательного веса обнаруживается сразу же после его появления, а не в конце всей процедуры.

4.1. Оптимальные циклы в графах с двойными весами [24.9]

Во многих ситуациях возникает следующая задача. Дан граф, дугам которого приписаны два числа - вес и некоторое другое число Ьц. Нужно найти такой цикл Ф, для которого целевая функция

S и

.(ф) >