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

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

Описание алгоритма:

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

Заводятся два списка "фронта волны" NewFront и OldFront, а также переменная Time (текущее время).

OldFront:={ver1}; NewFront:={}; Time:=1.

Для каждой из вершин i, входящих в OldFront, просматриваются соседние вершины j, и если Times [j] = 0, то Times [j]=Time, NewFront:= NewFront + {j}; в переменную Previous [j] заносится номер i.

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

Если одна из веpшин совпадает с ver2, то найден кратчайший путь длины Time, переход к шагу 8.

OldFront:= NewFront; NewFront:={}; Time:=Time+1; возврат к шагу 4.

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

Max – максимальное количество узлов в графе, уменьшение приводит к убыстрению расчётов.

Параметры вызова процедуры:

· S – матрица смежности, задающая невзвешенный граф;

· ver1, ver2 – номера начального и конечного узлов искомого пути;

· Length - длина найденного пути;

· Path – массив с номерами узлов найденного пути.

Блок-схема алгоритма приведена на рис. 1.5.

Схема блока А:

Рис. 1.5. Блок-схема волнового алгоритма

Дата добавления: 2014-01-07