Список використаної літератури. Представлення результатів роботи програми

Вхідні дані

Представлення результатів роботи програми.

Цей шлях 0-10-9-8

Аналіз результатів розв’язання задачі.

Розв’язання задачі на контрольному прикладі

Де 0-∞

0

0

0

0

Зробивши 11- ітерацій отримали результат

Матриця відстаней:

Матриця шляхів:

Розрахувавши задачу методом Флойда, ми знайшли мінімальну відстань від заводу збірного бетону до будівельних майданчиків.

До п.8- найкоротша відстань 17.

Найдовший шлях до п.8 -21

Інтерфейс програми:

Результат:

Для порівняння даних розрахуємо шлях до вершини 8 на Дейкстра:

1. Г.А.Гайна навчальний посібник з дисципліни «Методи оптимізації:алгоритми,приклади,задачі»К.:КНУБА,2005.-144с.

2. Культин Н. Б. Программирование в Turbo Pascal 7.0 – Спб.: БХВ – Санкт-Петербург, 1999 – 240 с.

Додаток 1.

Текст програми

procedure TForm1.DejkstraClick(Sender: TObject);

var v:integer;

fl:array[0..100] of boolean;

mas:array[0..100] of real;

i,j,min:integer;

begin

v:=StrToInt(LabeledEdit1.Text);

for j:=1 to n do

begin

fl[j]:=false;

mas[j]:=10000;

end;

for i:=1 to n do

for j:=1 to n do

if x[i,j]=0 then x[i,j]:=1000000;

fl[0]:=true;

mas[v]:=0;

//mas[0]:=10000+1;

for i:=1 to n do

begin

min:=1;

for j:=1 to n do

if (mas[j]<mas[min]) and (not fl[j]) then min:=j;

fl[min]:=true;

for j:=1 to n do

if (mas[j]>mas[min]+x[min,j]) then

mas[j]:=mas[min]+x[min,j];

end;

StringGrid4.RowCount:=3;

StringGrid4.ColCount:=n+1;

for i:=1 to n do

begin

StringGrid4.Cells[i,1]:=IntToStr(i);

StringGrid4.Cells[i,2]:=FloatToStr(mas[i]);

end;

end;

//******************************************************************************

procedure TForm1.SavDejkClick(Sender: TObject);

var i,j:integer;

FN:string; Fl:TextFile;

begin

SaveDialog1.Execute;

FN:=SaveDialog1.FileName;

AssignFile(Fl,FN);

Rewrite(Fl);

writeln(Fl,'Результат обчислення! Алгоритм Дейкстри');

for i:=1 to StringGrid4.ColCount do

begin

for j:=0 to StringGrid4.RowCount do

begin

write(Fl,StringGrid4.Cells[i,j]);

write(Fl,' ');

end;

writeln(Fl,' ');

end;

CloseFile(Fl);

end;

//*********************************Алгоритм Флойда******************************

procedure TForm1.FlojdClick(Sender: TObject);

var s:array[1..50,1..50] of integer;

d:array[1..50,1..50] of real;

i,j,k:integer;

besk:real;

begin

//

besk:=100000;

for i:=1 to n do

for j:=1 to n do

begin

if (i<>j) and (x[i,j]=0) then

d[i,j]:=besk

else d[i,j]:=x[i,j];

if i=j then s[i,j]:=0

else s[i][j]:=j;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if d[i,j]>(d[i,k]+d[k,j]) then

begin

d[i,j]:=d[i,k]+d[k,j];

s[i,j]:=k;

end;

StringGrid2.ColCount:=n+1;

StringGrid2.RowCount:=n+1;

StringGrid3.ColCount:=n+1;

StringGrid3.RowCount:=n+1;

for i:=1 to n do

for j:=1 to n do

begin

StringGrid2.Cells[j,i]:=FloatToStr(d[i,j]);

StringGrid3.Cells[j,i]:=IntToStr(s[i,j]);

end;

end;

Дата добавления: 2015-08-31