unit road2_;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Grids;

type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Button1: TButton;
    Label4: TLabel;
    procedure FormActivate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.FormActivate(Sender: TObject);
var
   i:integer;
begin
   // нумерация строк
   for i:=1 to 10 do
       StringGrid1.Cells[0,i]:=IntToStr(i);
   // нумерация колонок
   for i:=1 to 10 do
       StringGrid1.Cells[i,0]:=IntToStr(i);
   // описание предопределенной карты
   StringGrid1.Cells[1,2]:='1';
   StringGrid1.Cells[2,1]:='1';
   StringGrid1.Cells[1,3]:='1';
   StringGrid1.Cells[3,1]:='1';
   StringGrid1.Cells[1,4]:='1';
   StringGrid1.Cells[4,1]:='1';
   StringGrid1.Cells[3,7]:='1';
   StringGrid1.Cells[7,3]:='1';
   StringGrid1.Cells[4,6]:='1';
   StringGrid1.Cells[6,4]:='1';
   StringGrid1.Cells[5,6]:='1';
   StringGrid1.Cells[6,5]:='1';
   StringGrid1.Cells[5,7]:='1';
   StringGrid1.Cells[7,5]:='1';
   StringGrid1.Cells[6,7]:='1';
   StringGrid1.Cells[7,6]:='1';
end;


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[i]равен TRUE, если точка с номером i включена в road }
   start,finish:integer;          { Начальная и конечная точки }
   found:boolean;
   len:integer;                   { длинна найденного (минимального) маршрута }
   c_len:integer;                 { длина текущего (формируемого) маршрута }
   i,j:integer;

procedure step(s,f,p:integer);
  var
    c: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:=1 to N do { проверяем все вершины }
          if(map[s,c]<> 0)and(NOT incl[c])
             and((len=0)or(c_len+map[s,c]< len))

          then begin { точка соединена с текущей, но не включена в маршрут}
              road[p]:=c;{ добавим вершину в путь }
	      incl[c]:=TRUE;{ пометим вершину как включенную }
	      c_len:=c_len+map[s,c];
	      step(c,f,p+1);
	      incl[c]:=FALSE;
	      road[p]:=0;
	      c_len:=c_len-map[s,c];
          end;
end;{ конец процедуры step }

begin
   Label1.caption:='';
   { инициализация массивов }
   for i:=1 to N do road[i]:=0;
   for i:=1 to N do incl[i]:=FALSE;

   { ввод описания карты из SrtingGrid.Cells}
   for i:=1 to N do
       for j:=1 to N do
          if StringGrid1.Cells[i,j] <> ''
              then map[i,j]:=StrToInt(StringGrid1.Cells[i,j])
              else map[i,j]:=0;

   len:=0;   // длина найденного (минимального) маршрута
   c_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;
end.
