Поиск кратчайшего пути
Листинг 12.6. Поиск кратчайшего пути
procedure TForm1.Button1Click(Sender: TObject);
const
N=10;{ кол-во вершин графа} var
map:array[1..N,1..N]of integer;
// Карта.map[i,j] не 0,если
// точки i и j соединены
road:array[1..N]of integer;
// Дорога — номера точек карты
incl:array[1..N]of boolean; // incl[1]равен TRUE,если точка
// с номером i включена в road
start, finish:integer;
// Начальная и конечная точки
found:boolean; len:integer; // длина найденного (минимального)
// маршрута } c_len:integer; // длина текущего (формируемого)
// маршрута i,j:integer;
// выбор очередной точки
procedure step(s,f,p:integer);
var
с:integer; { Номер точки, в которую делаем очередной шаг }
i:integer; begin
if s=f then begin
len:=c_len;{ сохраним длину найденного маршрута }
{ вывод найденного маршрута }
for i:=1 to p-1 do
Label1.caption:=Label1.caption+' '+IntToStr(road[i]);
Label1.caption:=Label1.caption
+', длина:'+IntToStr(len)+#13;
end
else
{ выбираем очередную точку }
for c:=l to N do { проверяем все вершины }
if(map[s,c]<>
0)and(NOT incite])
and((len=0)or(c_len+map[s,c]< len)) then begin
// точка соединена с текущей, но не включена в
// маршрут
roadtp]:=c;{ добавим вершину в путь }
incl[c]:=TRUE;{ пометим вершину как включенную }
c_len:=c_len+map[s,с];
step(c,f,p+l);
incite]:=FALSE; roadtp]:=0;
c_len:=c_len-map[s,с];
end;
end;
{ конец процедуры step }
begin
Labell.caption:='';
{ инициализация массивов }
for i: =1 to N do road [ i ] : =0;
for i:=l to N do incl[i]:=FALSE;
{ ввод описания карты из SrtingGrid.Cells}
for i:=l to N do
for j:=1 to N do
if StringGridl.Cells[i, j] <>
"
then mapti,j]:=StrToInt(StringGridl.Cells[i,j])
else mapti,j]:=0;
len:=0; // длина найденного (минимального) маршрута с
len:=0,- // длина текущего (формируемого) маршрута
start:=StrToInt(Edit1.text);
finish:=StrToInt(Edit2.text);
road[1]:=start;{ внесем точку в маршрут }
incl[start]:=TRUE;{ пометим ее как включенную }
step(start,finish,2);
{ищем вторую точку маршрута }
// проверим, найден ли хотя бы один путь
if not found
then Label1.caption:='Указанные точки не соединены!';
end;
Диалоговое окно программы поиска кратчайшего пути и процедура обработки события OnActivate ничем не отличаются от диалогового окна и соответствующей процедуры OnActivate программы поиска всех возможных маршрутов, рассмотренной в предыдущем разделе.
