Программирование на языке Pascal
6cac1dc9

Реализация


Пусть граф задан матрицей смежности sm, а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути "на возврате" совершается рекурсией автоматически, поскольку в ее заголовке использован параметр-значение, а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром-значением чересчур накладно:

procedure rasst(v: byte; r: longint); var i: byte; begin if v = t then if r< min then min:= r else else for i:= 1 to N do if (mark[i]=0)and(sm[v,i]<>0) then begin mark[i]:=1; rasst(i,r+sm[v,i]); mark[i]:=0 end end;

begin ... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; mark[s]:= 1; rasst(s,0); mark[s]:= 0; ... end.



Содержание раздела