Реализация. Нахождение кратчайших путей

Алгоритм Расст-Рек

Рекурсивный алгоритм

Нахождение кратчайших путей

Задача. В заданном взвешенном связном графе найти расстояние (длину кратчайшего пути) от выделенной вершины s до вершины t. Веса всех ребер строго положительны.

Совершить обход графа в глубину, при каждом "шаге вперед" прибавляя длину ребра к длине текущего пути, при каждом возврате - отнимая длину этого ребра от длины текущего пути. При движении "вперед" пометки посещенности вершин ставятся, при "откате" - снимаются. По достижении выделенной вершины t производится сравнение длины текущего пути с ранее найденным минимумом.

Пусть граф задан матрицей смежности 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 endend; begin... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; mark[s]:= 1; rasst(s,0); mark[s]:= 0;...end.

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