end for end if

Обоснование. Достаточно заметить, что любой контур принадлежит ровно одной КСС, и, более того, если в КСС входит несколько узлов, то они обязательно принадлежат некоторым контурам. Поэтому, если при обходе в глубину мы попадаем в уже отмеченный узел u, то это означает, что обнаружен контур. Причем предшествующие узлы найденного контура находятся на стеке, начиная от его вершины и до рассматриваемого отмеченного узла u, который также присутствует в стеке. Все узлы найденного контура можно «склеить». При склеивании узла w его список смежности и список уже найденных узлов той КСС, которой принадлежит узел w, объединяются с соответствующими списками узла u. После этого можно продолжить поиск в глубину от узла и, который для этой цели следует оставить в стеке.

2.7. Алгоритмы нахождения кратчайших путей

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

Рассмотрим четыре классических алгоритма нахождения кратчайших путей.

Алгоритм Уоршалла позволяет ответить на вопрос, достижима ли вершина x из вершины u, т. е. существует ли цепь u, x . Очень часто бывает необходимо не только определить, существует ли цепь, но и найти эту цепь.

Если задан орграф G (X, V), в котором дуги нагружены числами (эти числа обычно называют весами или длинами дуг), то этот орграф можно представить в виде матрицы весов (длин) C:

0, дляi j;

С[i, j] cij , конечная величина, если есть дуга из узлаi в узел j;

, если нет дуги из узла i в узел j.

Длиной пути называется сумма длин дуг, входящих в этот путь.

Данное представление, равно как и последующие алгоритмы, применимы как к графам, так и к орграфам.

Алгоритм Флойда

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин (узлов) в (ор)графе. В этом алгоритме для хранения информации о путях ис-

пользуется матрица Н: array [1...p, 1...p] of 1...p, где

k, еслиk первая вершина, достигаемая на кратчайшем пути из i в j;

H[i, j]

0, если из вершины i в вершину j нет пути.

Вход: матрица С[1...р, 1...р] длин дуг.

Выход: матрица Т[1...р, 1...р] длин путей и матрица H[1...р, 1...р] самих путей.

for i from 1 to p do for j from 1 to p do

for k from 1 to p do

if i ≠ j & T[j, i] & i ≠ k & T[i, k] & (T[j, k] = T[j, к] > T[j, i] + Т[i, k]) then H[j, k] := H[j, i]

T[j, k] := T[j, i] + Т[i, k] end if

end for end for

for j from 1 to p do if T[j, i] < 0 then stop

end if end for

end for

Отступление. Матрица H размера О(р2) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе О(р2) путей, состоящих из О(р) вершин. Таким образом, непосредственное представление всех путей потребовало бы памяти объема О(р3). Экономия памяти достигается за счет интерпретации представления, т. е. динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном случае любой конкретный путь u, x легко извлекается из матрицы с помощью следующего алгоритма.

while w ≠ x do

w := H[w, x]; yield w {следующая вершина} end while

Если в G есть цикл с отрицательным весом, то решения поставленной задачи не существует, т. к. на этом цикле можно «накручивать» сколь угодно короткий путь.

Обоснование. Алгоритм Флойда имеет много общего с алгоритмом Уоршалла. Покажем по индукции, что после выполнения i-го шага основного цикла по i элементы матриц T[j, k] и H[j, k] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути из вершины j в вершину k, проходящем через промежуточные вершины из диапазона 1…i.

База: i = 0, т. е. до начала цикла элементы матриц T и H содержат информацию о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вершины. Пусть теперь перед началом выполнения тела цикла на i-м шаге T[j, k] содержит длину кратчайшего пути от j к k, а H[j, k] содержит первую вершину на кратчайшем пути из вершины j в вершину k (если таковой есть). В случае, если в результате добавления вершины i к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда i = р, матрицы содержат кратчайшие пути, проходящие через промежуточные вершины 1...р, т. е. искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Дополнительный цикл по j служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом.

Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами (узлами) в (ор)графе, если длины дуг неотрицательны.

Вход: орграф G(X, V), заданный матрицей длин дуг С: array [1...p, 1...p] of real; s и t – вершины графа.

Выход: векторы Т: array [1...p] of real и H: array [1...p] of 0...p. Если вершина v

лежит на кратчайшем пути от s к t, то T[x] – длина кратчайшего пути от s к v; H[x] – вершина, непосредственно предшествующая v на кратчайшем пути.

For x from 1 to р do

T[x] :=

γ[x] := 0 end for H[s] := 0

Т[s] := 0 γ[s] := 1 x := s

М:

for u Г(x) do

if γ[u] = 0 & Т[u] > T[x] + C[x, u] then

if X[u] = 0 & T[u] < m then x := u; m := T[u]

end if end for

if x = 0 then stop

end if

if x = t then stop

end if γ[x] := 1 goto M

Для применимости алгоритма Дейкстры достаточно выполнения неравенства треугольника:

(u, x, w) X (d(u, x) d(u, w) d(w, x)) ,

которое, очевидно, выполняется, если длины дуг неотрицательны. Если же допускаются отрицательные длины дуг, то алгоритм Дейкстры может оказаться неприменимым. Например, в графе с тремя узлами s, t и и, если C[s, t] = 2, C[s, u] = 3 и C[u, t] = –2, алгоритм не найдет кратчайшего пути длиной 1 и выдаст путь длиной 2.

Обоснование. Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве x используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[x] = 1, то T[x] = d(s, x), и все вершины на пути s, x , определяемом вектором H, обладают тем же свойством, т. е.

Действительно (по индукции), первый раз в качестве x используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны).

Пусть Т[и] = d(s, и) для всех ранее помеченных вершин u. Рассмотрим вновь помеченную вершину x, которая выбрана из условия:

T[x] min T[u] .

[u] 0

Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что

T[x] > d(s, x),

т. е. найденный путь, ведущий из s в x, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую, что γ[w] = 0. Имеем:

T[w] = d(s, w) d(s, x) < T[x],

что противоречит выбору вершины x.

Известно, что применение алгоритма Флойда в среднем примерно вдвое менее трудоемко, чем применение алгоритма Дейкстры для всех пар вершин.

Дерево кратчайших путей

Алгоритм Дейкстры можно использовать и в том случае, когда необходимо найти кратчайшие цепи (пути) от вершины s до всех остальных вершин.

Алгоритм Дейкстры применим как к графам, так и к орграфам в равной мере. Действительно, в этом алгоритме достаточно знать, какие вершины (узлы) являются соседними и какова цена (длина) перехода. Для графа матрица длин С и отношение смежности Г симметричны, для орграфа это не так, но для работы алгоритма Дейкстры данное обстоятельство не имеет значения. Таким образом, алгоритм, равно как и предшествующий, применим как к графам, так и к орграфам.

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

Вход: орграф G(X, V), заданный матрицей длин дуг и списками смежности Г; s – исходная вершина графа.

Выход: вектор Т: array [1...p] of real длин кратчайших путей от s.

for u X do Т[u] := C[s, u] γ[u] := 0

end for

for i from 1 to p do m :=

for u X do

if γ[u] = 0 & Т[u] < m then x := u, m := Т[u]

end if end for

for u Г(x) do

T[u] := min(T[u], T[x] + C[x, u]) {пересчет оценки длины пути из s в u через v} end for

γ[x] := 1 end for

Обоснование. Приведенный вариант алгоритма основан на той же идее, что и предшествующий: на очередном шаге необходимо выбрать вершину x, до которой точно известен кратчайший путь от s, и пересчитать оценки путей для вершин, смежных с x. Такой вершиной на первом шаге окажется вершина s (для нее T[s] = 0). На следующих шагах новой вершиной x является вершина, которая еще не рассмотрена (Х[и] = 0) и для которой оценка пути минимальна. Действительно, даже если в будущем обнаружится другой путь, ведущий в x, его длина будет больше.

Таким образом, грубая оценка трудоемкости алгоритма Дейкстры составляет O(р2), поскольку вложенные циклы выполняются О(р) раз. Заметим, что во внутреннем цикле явно совершается излишняя работа: вершины, далекие от s,

не могут повлиять на выбор x на ранних шагах, и их не стоит рассматривать раньше времени. Известно, что, подбирая структуры данных для представления графа более тщательно, можно уменьшить трудоемкость алгоритма Дейкстры до O{q log2p}.

Совокупность путей от вершины s к другим вершинам образует корневое дерево. Действительно, никакой кратчайший путь, очевидно, не содержит контуров (напомним, что длины дуг положительны). Всякий узел достижим из корня по построению. Более того, этот путь единственный, поскольку даже если в вершину ведет несколько кратчайших путей одинаковой длины, алгоритм выберет только один из них.

Кратчайшие пути в бесконтурном орграфе

Алгоритм Дейкстры применим, если длины дуг неотрицательны. Существует эффективный алгоритм, который позволяет найти дерево кратчайших путей в орграфе, даже если длины дуг отрицательны, но известно, что орграф не содержит контуров.

Лeммa. В произвольном бесконтурном орграфе G (X, V) узлы можно перенумеровать так, что (xi , x j ) V (i j) .

Доказательство. Отношение достижимости в бесконтурном графе есть строгое частичное упорядочение на конечном множестве. Применяя алгоритм топологической сортировки, получаем требуемую нумерацию слов.

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

АЛГОРИТМ ОПРЕДЕЛЕНИЯ РАССТОЯНИЙ ОТ ИСТОЧНИКА В БЕСКОНТУРНОМ ГРАФЕ

Вход: орграф G (X, V), заданный матрицей длин дуг С: array [1...p, 1...p] of real и списками предшествующих узлов Г–1; источник имеет номер 1.

Выход: вектор Т: array [1...p] of real длин кратчайших путей от источника.

Обоснование. Докажем индукцией по i, что основной цикл имеет инвариант

j 1...i (T[ j] d(1, j)) . База: если j = 1, то T[1] = 0 = d(1, 1). Пусть теперь

j i (T[ j] d(1, j)). В кратчайшем пути 1, i все промежуточные узлы имеют номера больше 1 и меньше i по построению орграфа, в частности, вершина j, предшествующая i на кратчайшем пути, будет выбрана во внутреннем цикле, для нее по индукционному предположению T[j] = d(1, j), и значит, T[i] = d(1, i).

В алгоритме используется множество «предшествования»

Г 1(x) def{u x Г(u)},

которое совпадает со списками смежности Г(x) для графов и не пересекается с Г(x) для направленных орграфов.