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

Вариант 1:

1) Вес ребра – 1 (нет ребра – 0). s – начало маршрута, t – конец маршрута.

Ищем маршрут между s и t.

2) Прямая фаза

Сначала все вершины не имеют меток.

Положим i = 0, присвоим вершине s вес w (s) = i (т.е. w (s) = 0).

Находим все не помеченные вершины, связанные ребром с вершиной (вершинами) с меткой i.

Если такие вершины есть, то помечаем их метками i = i + 1. Если вершина t помечена, то к п. 4. Если – нет, то к п. 2. Если таких вершин нет, а вершина t не помечена, то t недостижима из s. СТОП.

Длина кратчайшего маршрута от s к t равна w (t). СТОП.

3) Обратная фаза (начинается с конца)

Принадлежность вершин кратчайшему маршруту определяется из условий:

Конечная вершина v_k = t.

Для v_{k –1} должно выполняться условие w (t) – w (v_{k –1}) = 1.

Для v_{k– 2} w (v_{k– 1}) – w (v_{k –2}) = 1 и т.д. пока не придем в вершину s.