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

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

Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе G=(V,E) заданном матрицей связности S. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует волновой алгоритм.

Волновой алгоритм заключается в следующем:

1.каждой вершине i приписывается два целых числа T[i] - временная метка и P[i] - метка предыдущей вершины пути (начальное значение T[i]=0, P[i]=0 для всех i);

2.заводятся два списка "фронта волны" NF и OF, а также переменная T (текущее время);

3.OF:={u1}; NF:={}; T:=1;

4.для каждой из вершин i, входящих в OF, пpосматpиваются соседние вершины j

, и если T[j] = 0, то T[j]=T, NF=NF + {j}; в переменную P[j] заносится номер i.

5.если NF = {}, то путь не сyществyет, переход к шагу 8;

6.если одна из вершин совпадает с u2, то найден кратчайший путь длины T, переход к шагу 8;

7.OF:=NF; NF:={}; T:=T+1; возврат к шагу 4.

8.Восстанавливаем путь, проходя массив P.

В качестве OF, NF я использую массивы размера n (количество вершин в графе), некоторые языки (например, Pascal) позволяют работать с объектами типа множества, тогда правильнее использовать именно такую структуру для определения OF, NF, но для того чтобы не нарушать общности я все же остановился именно на массивах, которые присутствуют практически во всех языках программирования.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2) и массив Path содержащий последовательность номеров вершин определяющих путь.