Курсовая работа: Поиск кратчайшего пути в многоугольнике

if x3<x then L:=L+1;

end;

end;

y:=y+dy;

//WriteLn(fout,'L=',L);

if (L mod 2) =0 then b[m-j+1,i]:=0 else b[m-j+1,i]:=1;

end;

x:=x+dx;

end;

for i:=1 to m do begin

WriteLn(fout);

for j:=1 to m do begin

Write(fout,b[i,j]);

end;

end;

Поиск кратчайшего пути

Суть реализованного алгоритма состоит в том что, в соответствие булевой матрице, отражающей доступность точек, ставится целочисленная матрица меток. В её элементы записываются кол-ва ходов, за которое можно попасть из финиша в данную точку булевой матрицы. Когда устанавливается значение в метку, соответствующий старту начинается обратный ход. Программа ищет соседнюю старту точку, метка которой на 1 меньше метки старта. Далее из найденной точки повторяется та же операция и так до тех пор пока не будет достигнут финиш.

procedure Tgraph.find(var z:Tmatrix;a,b:Txy;n:Integer);

var i,j,i1,j1:integer;

c:Integer;//для записи значений в метки

yyy:Boolean;//используется как условие выхода из цикла

LABEL LBL;

begin

ny:=0;//длина пути

//зополнение матрицы меток бесконечностями

for i:=0 to n-1 do

for j:=0 to n-1 do metka1[i,j]:=$7fff;

metka1[b.x,b.y]:=0;//метка соответствующая финишу

//процедура записывает в конкретную метку кол-во ходов,