где Ti = (xj) П S. (Множество S содержит теперь все вершины, для которых кратчайшие пути из s состоят из А: дуг.)

Множество Ti содержит те вершины, для которых текуш;ие кратчайшие пути из s состоят из к дуг (т. е. те, вершины которых лежат ъ S) ш для которых суш;ествуют дуги к вершине аг. Отметим, что если Xj $ Г {S), то кратчайший путь от s к Xj не может СОСТОЯТЬ из А; 1 дуг и поэтому изменять пометку вершины Xj не нужно. Для вершин Х| $ Г (5) положим 1* (xj) = (xj).

Проверка на окончание

Шаг 3. (а) Если к п - 1 и (xj) = Z* (xj) для всех Xj, то получен оптимальный ответ и пометки равны длинам кратчайших путей. Останов.

(б) Если к <сп - 1 и г** (х,) Ф l (Xj) для некоторой вершины Xj, то перейти к шагу 4.

(в) Если к = п - 1 и (Xj) Ф (xj) для некоторой вершины Xj, то в графе существует цикл отрицательного веса и задача не имеет решения. Останов.

Подготовка к следующей итерации

Шаг 4. Обновить множество следующим образом:

S{x,\l*{x,)ф,l(Xi)}. (8.4)

(Новое множество S содержит теперь все вершины, кратчайшие пути до которых из S имеют длину А; -f 1.)

Шаг 5. Положить к = к + i и перейти к шагу 2.

Как только получены длины кратчайших путей от s к каждой другой вершине, то сами пути опять находятся просто, с помощью соотношения (8.2). Пути могут быть получены и другим способом, если в дополнение к пометке (Xj) для каждой вершины хранить во время вычислений другую пометку в* (xj). Пометка в* (xj) указывает вершину, непосредственно предшествующую вершине Xi в кратчай шем пути от s к Xj во время к-& итерации. Можно начать с 6 (Xj) = sV Xj 6 Г (s) и для всех остальных вершин Xj выбрать 6 (Xj) произвольно (скажем, равной 0). Пометки 6* (xj) можно тогда изменять в соответствии с соотношением (8.3). Таким образом, 6** (xj) = (Xj), если в квадратных скобках в выражении (8.3) будет наименьшим первый член, или 6** (xj) = xj, если наименьшим является второй член. Если в (Xj) - вектор, составленный из пометок 6 при завершении работы алгоритма, то кратчайший путь от S к Xj получается в обратном порядке, а именно s, . . ., 6 (Xj), 6* (xj), в (Xj), Xj, где 6* (xj) является сокращением для 6 (G (х,)) и т. д.

Доказательство того, что приведенный алгоритм дает оптимальное решение, весьма простое. Здесь мы его не приводим. Одна-

ко заметим, что оно базируется на принципе динамического программирования и том факте, что если не суп1;ествувт никакого оптимального пути из к pjv, то не может также суш;ествовать и никакого оптимального пути, содержащего к + i дуг [4]. Описанный алгоритм можно применять и в случав неотрицательной матрицы весов, хотя это, вообще говоря, намного хуже, чем использование алгоритма Дейкстры. В случае полного связного графа с п вершинами этот алгоритм требует порядка и* операций сложения и сравнения, в то время как в алгоритме Дейкстры требуется га* операций. Некоторые улучшения описанного алгоритма, предложенные Йеном, позволяют уменьшить число операций в четыре раза, но порядок роста остается равным трем.

2.2.2. Пример. Рассмотрим граф, изображенный на рис. 8.3, где опять неориентированные ребра рассматриваются как нары

20 -13

Рис. 8.3. Граф из примера 2.2.2.

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

Алгоритм работает следующим образом.

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

Шаг 2. S = xi, 5 = {х^, х,}, V- {ху) = О, (х^) = -3, V- (х,) = 2, 1 (xi) - оо для всех других х^. Положить к = i.

Первая итерация

Шаг 2. Г {S) = {х^, х^, х^, х^, х^}. Поэтому для : = = {xi, Xg} n {Xi, Xs} = {xs} и из соотношения (8.3) получаем

Z2 (Хг) = min [ - 3, {г^(х5)+с(х5, Ха)}] = = min[-3, (2 + 12)] =

для Хз: Тз = {xz, Х4, Х7, Xg} П {х^, Xj} = {хг}, /2(хз) = т1п[схэ, ( - 3 - 5)]= -8;

для Х4: Г4 = (Хг, Хз, Xs, Х7, Х9} П {а;2, Xs} = {хг, Хд},

Z2(x4) = min[oo, min {( - 3 + 15), (2 -7)}]= -5;

для Xs: Ts = (xi, X2 xe} П {xz, Xs} = {xa}, Z2 (Xs) = min [2, (- 3 + 12)] = 2;

ДЛЯ Xe: Tg = {X4, Xg, X7, Xg} n {X2, Xg} = {Xg},

Z2(x6) = min[oo, (2+ 20)] = 22.

Пометки (Xj) таковы: [0, -3, -8, -5, 2, 22, oo, 00, 00] для = Xi, Xj, . . ., X9 соответственно.

Жаг 5 (б). Перейти к шагу 4.

Шаг 4. S = (хз, Х4, Xg}.

Шаг 5. к = 2, перейти к шагу 2.

Вторая итерация

Шаг 2. Г {S) = {xi, Х3, Х4, Xg, Xg, Х7, Xg, Xg}; для Хз: Гз = (хг, Х4, Х7, Xg} fl {хз, х^, х^} = {Х4}, V (хз) = т1п[-8, (-5 + 8)]= -8;

ДЛЯ Х4: Г4 = {Х2, Хз, Xg, Х7, Xg} n (3:3, Xi, Xe} = {Хз}, Z3(x4) = min{-5, ( - 8 + 8)]= -5;