Волновой алгоритм

Дано: непyстой гpаф G=(V,E). Требуется найти путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер).

I.

1. каждой вершине v_i приписывается целое число T(v_i) - волновая метка (начальное значение T(v_i)=-1);

2. заводятся два списка OldFront и NewFront (старый и новый "фpонт волны"), а также пеpеменная T (текyщее вpемя);

3. OldFront:={s}; NewFront:={}; T(s):=0; T:=0;

4. для каждой из веpшин, входящих в OldFront, пpосматpиваются инцидентные (смежные) ей веpшины u_j, и если T(u_j) = -1, то T(u_j):=T+1, NewFront:=NewFront + {u_j};

5. если NewFront = {}, то ВЫХОД("нет решения");

6. если t  NewFront (т.е. одна из веpшин u_j совпадает t), то найден кpатчайший пyть между s и t с T(t)=T+1 промежуточными ребрами; ВЫХОД("решение найдено");

7. OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4).

Замечание: на шаге (4) "соседними" вершинами для неориентированных графов считаются все смежные вершины, а для орграфов - вершины, в которые из данной вершины ведут дуги.

II.

Если на шаге (6) была достигнyта веpшина t, то восстановить кpатчайший пyть можно следyющим обpазом: сpеди соседей веpшины t найдем любую веpшину с волновой меткой T(t)-1, сpеди соседей последней - веpшину с меткой T(t)-2, и т.д., пока не достигнем s. Найденная последовательность вершин определяет один из кpатчайших пyтей из s в t. Hа пpактике выгодно сохpанять на шаге (4) инфоpмацию о том, из какой веpшины "волна" пpишла в веpшинy u_j - тогда восстановление пyти осyществляется быстpее.

Разметка графа после выполнения волнового алгоритма.

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

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

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

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

Будем называть итерацией волнового алгоритма очередное выполнение шагов (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)=, -1) => (d(s,v_i)=)).

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.

В библиотеке AGraph реализованы различные варианты волнового алгоритма.

Пути минимального суммарного веса во взвешенном графе

Задача: найти путь (один из путей) минимальной суммарной длины между двумя заданными вершинами взвешенного графа (орграфа) с неотрицательными весами ребер (дуг).

Классическим алгоритмом решения данной задачи является алгоритм Дейкстры. При эффективной реализации временн'ая сложность алгоритма в худшем случае равна O(m+n log n), где m=|E|, n=|V|.

Пример прикладной задачи: необходимо добраться на самолете из города A в город B при условии, что между ними нет прямого авиационного сообщения, затратив при этом минимальные средства (при условии, что заданы возможные промежуточные аэропорты, для каждой пары аэропортов известно, существует ли между ними прямой маршрут, и если да, то известна минимальная стоимость перелета по этому маршруту).

Решение: построим взвешенный граф (орграф - если бывают "несимметричные" маршруты), вершины которого соответствуют всем возможным аэропортам, ребра (дуги) - прямым маршрутам между ними, а веса ребер (дуг) равны стоимости перелета (очевидно, неотрицательной) между соответствующими аэропортами. Задача сводится к нахождению в графе (орграфе) пути минимального веса между вершинами, соответствующими A и B.