Вариант 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) Обратная фаза (начинается с конца)
Принадлежность вершин кратчайшему маршруту определяется из условий:
Конечная вершина vk = t.
Для vk –1 должно выполняться условие w (t) – w (vk –1) = 1.
Для vk– 2 w (vk– 1) – w (vk –2) = 1 и т.д. пока не придем в вершину s.