Шаг 11.
Основные понятия теории графов.
Доказательство корректности волнового алгоритма

    На этом шаге мы рассмотрим доказательство корректности волнового алгоритма.

    Под корректностью алгоритма здесь понимается, что:

1. Алгоритм завершает работу за конечное время;
2. Если решение существует, то алгоритм находит правильное решение.

    Будем называть итерацией волнового алгоритма очередное выполнение шагов (4)-(7) алгоритма.

    A.

    Волновой алгоритм завершает работу за конечное число итераций - это следует из конечности графа, а также из того, что на каждой итерации либо происходит уменьшение количества вершин графа, волновая метка которых равна "-1" (на шаге 4), либо завершение работы алгоритма (на шаге 5).

    B.

1. Докажем по индукции, что (*) к началу выполнения шага (4) алгоритма при заданном значении T волновые метки всех вершин v_i, таких, что расстояние (т.е. количество ребер в кратчайшем пути) между s и v_i равно T, также равны T ((d(s,v_i)=T) => (T(v_i)=T)), и, кроме того, все эти вершины находятся в списке OldFront. Базис индукции: при T=0 утверждение (*) выполняется (единственной вершиной, находящейся на расстоянии 0 от s, является сама вершина s; на шаге (3) она получит волновую метку 0 и будет занесена в OldFront); при T=1 утверждение (*) также выполняется (т.к. при T=0 все вершины, инцидентные s, получат волновую метку 1 и попадут сначала в NewFront, а затем, на шаге (7) алгоритма, в OldFront). Допустим, что (**) утверждение (*) выполняется для всех T<T₀ (T₀>1). Рассмотрим все вершины u_j, находящиеся на расстоянии T₀ от s: d(s,u_j)=T₀. Запишем кратчайший путь из s в u_j в виде L=(s(s,w₁)w₁...(w_k,u_j)u_j), где k=T₀-1. Путь L'=(s(s,w₁)w₁...(w_k-1,w_k)w_k) является кратчайшим путем из s в w_k (в противном случае L не являлся бы кратчайшим путем из s в u_j), его длина T'=T₀-1<T₀, поэтому в силу (**) к началу выполнения шага (4) алгоритма при T=T', во-первых, T(w_k)=T', и, во-вторых, w_k находится в OldFront. Вершины w_k и u_j являются смежными, поэтому на шаге (4) вершина u_j получит волновую метку T'+1=T₀ и попадет в NewFront. На шаге (7) значение T будет увеличено на единицу, а NewFront скопирован в OldFront, следовательно, утверждение (*) будет выполняться при T=T₀.
2. Поскольку при работе алгоритма T "пробегает" все целые значения, начиная с 0 и кончая некоторым целым числом, большим либо равным 0, из 1 следует, что если волновая метка вершины не равна -1, то она равна расстоянию между s и этой вершиной ((T(v_i)=a, a≠-1) => (d(s,v_i)=a)).
3. Докажем, что (*) если решение существует, т.е. существует кратчайший путь из s в t длины d(s,t), то выполнение шага (4) при T'=d(s,t)-1 будет иметь место. Единственной возможностью для завершения работы алгоритма при некотором T''<T' является выход на шаге (5), но такой выход возможен тогда и только тогда, когда (**) ни одна из вершин, находящихся на расстоянии T'' от s, не имеет инцидентных вершин, находящихся на расстоянии, большем T'', от s. Действительно, выход на шаге (5) происходит, если и только если список NewFront пуст, а это возможно, если и только если на данной итерации все вершины, инцидентные вершинам из OldFront, имеют волновые метки, не равные -1. Волновые метки этих вершин не могут быть больше T'' (т.к. отличные от -1 значения были присвоены им на итерациях алгоритма при T<T''), следовательно, волновые метки находятся в диапазоне [0..T'']. В силу 2 волновые метки вершин, не равные -1, равны расстояниям между s и этими вершинами, что и доказывает (**). Из (**) cледует, что путей между s и вершинами, находящимися на расстоянии T>T'', в том числе между s и t, не существует. Значит, выход на шаге (5) при T''<T' не может произойти и утверждение (*) верно.
4. Из 1-3 следует: (*) волновые метки вершин v_i, находящихся на расстоянии, меньшем d(s,t), от s, равны этому расстоянию ((d(v_i,s)<d(s,t)) => (T(v_i)=d(v_i,s))); (**) на некоторой итерации вершина t получит волновую метку d(s,t) и попадет в NewFront, следовательно, алгоритм завершится на шаге (6) той же итерации. Корректность используемого способа восстановления кратчайшего пути по волновым меткам вершин следует из (*).

    Существуют модификации приведенного здесь алгоритма, позволяющие находить:

1. кратчайшие пути между s и всеми другими вершинами графа;
2. все кратчайшие пути (либо не более чем заданное количество путей) между s и t.

    На следующем шаге мы рассмотрим пути минимального суммарного веса во взвешенном графе.

Предыдущий шаг Содержание Следующий шаг