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

Если текущая вершина - конечная (vB), то делаем " ... сравнение пути с оптимальным"

Иначе проверяем, если текущая дуга еще не использовась (color[i,j]=FREE) то делаем "... продолжение пути с вызовом DFS".

При этом, перед входом в DFS помечаем дугу как использованную (color[i,j]:=DONE), а после выхода - как вновь свободную (color[i,j]:=FREE);

"... продолжение пути с вызовом DFS" включает в себя следующие операторы:

inc(kv); sled[kv]:=G[i,j,1]; { помещаем в путь новую вершину }

NewTime:=Time[i]+G[i,j,2]+CountTime; {вычисляемновоевремя}

if NewTime<OptT {если новое время меньше оптимального}

then {то продолжаем,иначе - отсекаем}

begin

color[i,j]:=DONE; { Помечаем - ребро использовано }

RetTime:=Time[G[i,j,1]]; { Сохраняем старое время }

Time[G[i,j,1]]:=NewTime; { Устанавливаем новое время }

DFS(G[i,j,1]); { Вызываем поиск от G[i,j,1] }

Time[G[i,j,1]]:=RetTime; { Восстанавливаем старое время }

color[i,j]:=FREE; { Помечаем - ребро свободно }

end;

Sled[kv]:=0; dec(kv); { Удаляем вершину из пути }

Для вычисления нового времени здесь используется функция CounTime с параметром kv - номер последней вершины в стеке.Эта функция делает следующее: Восстанавливает номера вершин, прохода через перекресток "из i1 через i2 в i3":

if kv=2 then begin CountTime:=0; exit; end;

i1 := sled[kv-2];

i2 := sled[kv-1];

i3 := sled[kv];

if i3=i1 then begin CountTime:=K*D[i2]; exit; end;

Попутно, выясняется

а) если вершин в пути всего 2, то есть не было никакого поворота - это шаг из начальной вершины и CountTime=0.

б) если i1=i3 то это поворот на 180 градусов и авторы задачи считают, что это тоже левый поворот, CountTime=K*D[i2]; где, K - коэффициент который вводится, i2 - перекресток, D[i2] - количество дорог, входящих в этот перекресток.

Затем из массивов координат перекрестков выбираются координаты текущих перекрестков: (x1,y1) (откуда); (x2,y2) (через какой); (x3,y3) (куда).

x1 := x[i1]; x2:=x[i2]; x3:=x[i3];

y1 := y[i1]; y2:=y[i2]; y3:=y[i3];