56 4. Пути в сетях
Можно отметить, что тогда D(w) определяет длину минимального
(s, w)-пути среди всех (s, w)-путей, все вершины в котором, кроме w,
принадлежат S.
Выберем теперь такую вершину w
∗
∈ F , что выпо лнено условие:
D(w
∗
) = min{D(w)|w ∈ F }.
Оказывается, что вершина w
∗
является самой близкой к s среди всех
вершин, не входящих в S (она является следующей (k+1)-ой ближайшей
к s вершиной), и, более того, расстояние от вершины s до вершины w
∗
в точности равно D(w
∗
), т. е. справедливо равенство d(w
∗
) = D(w
∗
).
Обоснуем вначале равенство d(w
∗
) = D(w
∗
). Пусть P : s = w
0
,
w
1
. . . , w
r
= w
∗
— произвольный (s, w
∗
)-путь в сети G. Достаточно до-
казать неравенство D(w
∗
) 6 c(P ). Среди всех вершин пути P выберем
вершину w
j
с наименьшим номером среди тех, которые не в ходят в мно-
жество S. Так как начальная вершина пути P входит в S, а конечная
— не входит в S, то такой номер j найдется. Итак w
j−1
∈ S, w
j
∈ F .
Тогда, из определения D[w], где w ∈ F , и определения стоимости пути
вытекают неравенства
D(w
j
) 6 d(w
j−1
) + c(w
j−1
, w
j
) 6
6 c(w
0
, w
1
) + . . . + c(w
j−1
, w
j
) = с(Q),
где через Q обозначен (s, w
j
)-подпуть пути P . Из условия неотрица-
тельности весов дуг вытекает, что c(Q) 6 c(P ). Кроме того, по выбору
вершины w следует, что D(w
∗
) 6 D(w
j
). С учетом этих неравенств по-
лучаем, что D(w
∗
) 6 c(P ). Следовательно, d(w
∗
) = D(w
∗
).
Осталось убедиться, что вершина w
∗
является (k + 1)-ой ближайшей
к s вершиной. Для этого достаточно доказать неравенство d(w
∗
) 6 d(w)
для всех w ∈ F . Зафиксируем (s, w
∗
)-путь P
1
и (s, w)-путь P
2
, для ко-
торых c(P
1
) = d(w
∗
) и c(P
2
) = d(w). В силу доказанного только что
равенства D(w
∗
) = d(w
∗
) можно считать, что в пути P
1
все верши-
ны, кроме w
∗
, лежат в S. Тогда, по выбору вершины w
∗
, справедливо
неравенство D(w
∗
) 6 D(w), и, повторяя вышеприведенные рассужде-
ния, приходим к неравенству D(w) 6 c(P ). Отсюда c(P
1
) = d(w
∗
) =
= D(w
∗
) 6 c(P
2
) = d(w), что и требовалось доказать.
Итак, выбирая вершину w ∈ F с минимальным значением D[v] и
добавляя к S, мы расширяем множество вершин, до которых вычислено
расстояние, на один элемент. Следовательно, повторяя n−1 раз процесс
расширения множества S, мы вычислим расстояния до всех вершин сети
G.