unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
var
i: integer;
begin
// нумерация строк
for i:=l to 10 do
StringGrid1. Cells [0,i] :=IntToStr (i) ;
// нумерация колонок
for i:=l to 10 do
StringGridl.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.
begin
end;
//procedure TForm1.Button1Click(Sender: TObject);
//begin
procedure TForm1.ButtonlClick(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;
end;
end.
05.06.2011, 23:36
Минимальный путь графа
Линейный вид
