Рис. 25.3 25.3 Релаксация ребра (u, v). В вершинах указаны оценки кратчайшего пути, (а) Поскольку перед релаксацией было d[v] > d[u]-\-w(u, v), в результате релаксации d[v] уменьшается, (б) Уже до релаксации имеем d[v] d[u] + w(u, v). Релаксация ничего не меняет.

граф с весовой функцией w: Е -> Ж; пусть s £ V. Тогда для всякого ребра (и, v) £ Е имеем S(s, v) S(s, и) + w(u, v). Доказательство.

Вес кратчайшего пути из s в v не превосходит веса любого пути из s в v, в том числе и проходящего на последнем шаге через и. Релаксация

Техника релаксации, которая уже упоминалась выше, состоит в следующем. Для каждого ребра v £ V мы храним некоторое число d[v], являющееся верхней оценкой веса кратчайшего пути из s в v; для краткости мы будем называть его просто оценкой кратчайшего пути (shortest-path estimate). Начальное значение оценки кратчайшего пути (и предшественников) даётся следующей процедурой:

Initialize-Single-Source(G,s)

1for (для) всех вершин v \in V[G]

2do d[v] \gets \infty

3\pi[v] \gets \text{\sc nil}

4d[s] \gets 0

Иными словами, первоначально ir[v] = nil для всех v; при этом d[s] = 0 и d[v] = оо для остальных вершин v.

Релаксация ребра (и, v) £ Е состоит в следующем: значение d[v] уменьшается до d[u] + w(u,v) (если второе значение меньше первого): при этом d[v] остаётся верхней оценкой в силу леммы 25.3. Мы хотим, чтобы ir[v] указывали на путь, использованный при получении этой верхней оценки, поэтому одновременно мы меняем значение ir[v]:

Relax(u,v,w)

1if d[v] > d[u] + w(u,v)

2then d[v] \gets d[u] + w(u,v)

3\pi[v] \gets u

На рис. 25.3 приведены два примера релаксации: в одном случае оценка кратчайшего пути уменьшается, в другом ничего не происходит.

Алгоритмы, описываемые в этой главе, устроены так: они вызывают процедуру Initialize-Single-Source, а затем производят релаксацию рёбер. Разные алгоритмы отличаются порядком, в котором рёбра подвергаются релаксации. В алгоритме Дейкстры и алгоритме для ациклических графов каждое ребро подвергается

релаксации лишь единожды. В алгоритме Беллмана-Форда рёбра подвергаются релаксации по нескольку раз. Свойства релаксации

Леммы, доказываемые в этом и следующем разделах, будут использованы при доказательстве правильности алгоритмов поиска кратчайших путей.

Следующая лемма очевидна.

Лемма 25.4

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w: Е -> Ж, и пусть (и, v) £ Е. Тогда сразу же после релаксации этого ребра (вызова Relax(m, v, w)) выполняется неравенство d[v] d[u] + w(u, v).

Лемма 25.5

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w; пусть s £ V - начальная вершина. Тогда после выполнения процедуры Initialize-Single-Source(C, s), а затем произвольной последовательности операций релаксации рёбер, для каждой вершины v £ V выполнено неравенство d[v] S(s,v). Если при этом для какой-то из вершин v это неравенство обращается в равенство, то равенство d[v] = S(s,v) останется верным и в дальнейшем (при последующих релаксациях рёбер).

Доказательство

В самом деле, после инициализации значения d[v] бесконечны при v ф s (и потому являются оценкой сверху для чего угодно), a d[s] = 0 (что тоже правильно). В процессе релаксации значение d[v] остаётся верхней оценкой для S(s,v), поскольку

S(s, v) S(s, и) + w(u, v) d[u] + w(u, v)

(первое неравенство - по лемме 25.3).

Второе утверждение леммы: поскольку в процессе релаксации значения d могут только уменьшаются, а после достижения равенства d[v] = S(s, v) дальше уменьшаться некуда.

Следствие 25.6

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s. Пусть вершина v £ V недостижима из s. Тогда после исполнения процедуры Initialize-Single-Source(C, s) и любой последовательности релаксаций ребер значение d[v] будет оставаться бесконечным (и равным S(s, v)).

Следующая лемма играет основную роль при доказательстве правильности алгоритмов поиска кратчайших путей.

Лемма 25.7

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s. Пусть s и -> v - кратчайший путь с последним ребром (и, v) Предположим, что была исполнена процедура Initialize-Single-Source(C, s), а затем -

последовательность релаксаций некоторых ребер, включающая релаксацию ребра (и, v). Если в какой-то момент до релаксации ребра (и, v) выполнялось равенство d[u] = S(s,u), то в любой момент после релаксации (и, v) будет выполнено равенство d[v] = S(s,v). Доказательство

В самом деле, равенство d[u] = S(s,u) сохранится до момента релаксации ребра (и, v) (как, впрочем, и до любого дальнейшего момента, см. лемму 25.5). Поэтому сразу после релаксации ребра (и, v) имеем

d[v] d[u] + w(u, v) = S(s, и) + w(u, v) = S(s, v)

(последнее равенство - по следствию 25.2). Поскольку, с другой стороны, d[v] 8(s,v) по лемме 25.5, получаем, что d[v] = S(s,v) сразу после релаксации (а значит, и позже). Деревья кратчайших путей

Посмотрим, что происходит при наших операциях с подграфом предшествования Gv. Лемма 25.8

Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w и исходной вершиной s, причем в графе G нет циклов отрицательного веса, достижимых из s. Тогда после операции Initialize-Single-Source, s), за которой следует произвольная последовательность релаксаций рёбер, подграф предшественников Gv является деревом с корнем s.

Доказательство

Напомним, что вершинами графа Gv являются те вершины v £ V, для которых ir[v] ф nil, а также вершина s. Другими словами, в него входят те вершины v, для которых d[v] конечно (чтобы убедиться в этом, достаточно посмотреть на процедуру релаксации: при уменьшении d[v] происходит присваивание переменной 7г[г>]). Для каждой вершины v графа Gv в этот граф включается ребро с началом ir[v] и концом v. По построению это ребро является ребром исходного графа G.

Сразу после инициализации граф Gv состоит только из начальной вершины и тем самым является деревом. Мы будем доказывать по индукции, что он остаётся деревом после выполнения произвольной последовательности операций релаксации.

Когда в нём появляются новые вершины? Это происходит при выполнении операции релаксации ребра (и, v), до которой d[v] было бесконечным (а стало конечным - после релаксации любого ребра (ж, у) значение d[y] обязательно конечно). В этот момент ir[v] становится равным и, то есть к дереву Gv добавляется лист. При этом оно остаётся деревом.

Остаётся проверить, что граф Gv остаётся деревом и в том случае, когда при релаксации ребра (и, v) значение d[v] уменьшается от одного конечного значения до другого. Давайте посмотрим,