Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

Основной алгоритм выглядит следующим образом:

for i:=1 to N do

begin

for j:=1 to kG[i] do Color[i,j]:=WHITE; { вседугисвободны }

Time[i]:=maxlongint; { время маршрута до I - максимально }

end;

OptT:=Maxlongint; { Оптимальное время - максимально}

Sled[1]:=vA; { Заносим в маршрут вершину vA}

kv:=1; { Количество вершин в маршруте = 1}

Time[vA]:=0; { Оптимальное время до вершины vA =0}

DFS(vA); { Поиск в глубину от вершины vA }

вывод ответа

Рекурсивная процедура DFS(i) обеспечивает выполнение следующей работы:

Procedure DFS(i)

begin

for j:=1 to kG[i] do

if G[i,j,1]<>vB

then

begin

if color[i,j]=FREE

then

begin

продолжение пути с вызовом DFS

end

end

else

begin

сравнение пути с текущим оптимальным

end;