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

procedure DFS(v:byte);

var j : byte;

begin

for j:=1 to kG[v] do

if (color[v,j]=FREE)

then

begin

if (G[v,j]=B) and (LabC=1)

then begin OutRes; halt; end;

if G[v,j]=C then LabC:=1;

color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];

DFS(G[v,j]);

color[v,j]:=FREE; sled[ks]:=0; dec(ks);

if G[v,j]=C then LabC:=0;

end;

end;

То есть для всех еще необработанных (color[v,j]=FREE) дуг от текущей вершины выясняем - если она ведет в конечный пункт, а город C уже проходили - вызов процедуры вывода результата и останов.

Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1).

Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS - количество элементов в нем.

Вызываем процедуру DFS от вершины (G[v,j]), в которую ведет текущая дуга.

Перед выходом из процедуры DFS восстанавливаем состояние, "исходное" перед ее вызовом: снимаем отметку обработки с дуги ( color[v,j]:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled[ks]:=0; делать необязательно, но он предоставляет удобства отладки - что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы).

И, наконец, процедура вывода результата:

procedure OutRes;

begin

writeln(ks+2);

writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);

end;

Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2.

Полный текст программы приводится ниже.