Доказательство корректности

Пусть l(v) — длина кратчайшего пути из вершины a в вершину v. Докажем по индукции,

что в момент посещения любой вершины z, d(z)=l(z).

База. Первой посещается вершина a. В этот момент d(a)=l(a)=0.

Шаг. Пускай мы выбрали для посещения вершину z!= a. Докажем, что в этот момент d(z)=l(z).

Для начала отметим, что для любой вершины v, всегда выполняется d(v) >= l(v)

(алгоритм не может найти путь короче, чем кратчайший из всех существующих).

Пусть P — кратчайший путь из a в z, y — первая непосещённая вершина на P, x —

предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть,

ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По

предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x),

следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y).

Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её

метка минимальна среди непосещённых, то есть d(z)<=d(y) = l(y)<=l(z). Комбинируя это

с d(z)>=l(z), имеем d(z)=l(z), что и требовалось доказать. Поскольку алгоритм

заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.

19. Сети и потоки. Величина потока и его свойства (сумма потоков из источника = сумме потоков в сток). Задача о нахождении максимального потока.

Определение. Сетью называется взвешенный граф G = (E, V) с весовой функцией q: E → R+ в котором выделен источник A ∈ V,→deg(A) = 0, и сток B ∈ V, ←deg(B) = 0. Значение q(X, Y) называется пропускной способностью ребра (X, Y) ∈ E.

Если (X, Y) ∈/ E то считаем, что q(X, Y) = 0

Определение. Потоком называется весовая функция p: E → R+ ∪ {0} такая, что

1. p(X, Y) ≤ q(X, Y) для всех (X, Y) ∈ E;

2. Для всех вершин C!= A,B имеет место

p(C, X) = p(Y, C).

Если (X, Y) ∈/ E то считаем, что p(X, Y) = 0.Теорема. Для потока p: E 7→ R+ в сети G = (E, V, q, A, B)

имеет место

p(A, X) = p(Y, B).

Данная сумма называется величиной потока.

p(A, X) = p(C, X) − p(C, X) = p(Y, C) − p(Y, C) =

p(Y, B).

Задача о максимальном потоке.

Дано. Пусть имеется сеть G = (E, V, q, A, B).

Найти поток p: E → R+ ∪ {0} с наибольшей величиной V(p).