Ocena użytkownikóww: ***** / 0
Nadesłany przez Tomasz Lubiński, 09 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
floyd_d/Floyda.dpr:
//(c)2002 Tomasz Lubinski
//www.algorytm.org
//algorytm Floyda - minimalne odleglosci miedzy wierzcholkami w grafie, domkniecie zwrotne
program Floyda;
uses
Math,
SysUtils;
{$R *.RES}
{$Apptype console} //dyrektywa kompilatora - program dos'owy
type macierz = record
odl: Real; //odleglosc
droga: Boolean; //true - droga istnieje; false - droga nie istnieje
end;
var
i,j,k,n: Integer;
tmp: String;
A: array of array of macierz;
begin
writeln('Podaj liczbe wierzcholkow');
readln(n);
SetLength(A, n, n); //ustawienie rozmiaru macierzy A
writeln('Podaj wartosci macierzy odleglosci A');
writeln('Gdy miedzy wierzcholkami nie ma polaczenia wpisz niesk');
//wczytanie od uzytkownika odleglosci
for i:=0 to n-1 do
for j:=0 to n-1 do
begin
if i=j then begin A[i,j].odl:=0; A[i,j].droga:=true; continue; end;
write('A['+IntToStr(i)+','+IntToStr(j)+']=');
readln(tmp);
if tmp<>'niesk' then
begin
A[i,j].odl:=StrToFloat(tmp);
A[i,j].droga:=true;
end
else
begin
A[i,j].odl:=0;
A[i,j].droga:=false;
end;
end;
//algorytm Floyda
for k:=0 to n-1 do
for i:=0 to n-1 do
for j:=0 to n-1 do
begin
if (A[i,k].droga)and(A[k,j].droga) then
begin
if A[i,j].droga=false then
A[i,j].odl:=A[i,k].odl+A[k,j].odl //jesli droga i,j nie istnieje to musi to byc suma drog i,k+k,j
else
A[i,j].odl:=min(A[i,j].odl, A[i,k].odl+A[k,j].odl); //jesli istnieje to wybierz minimum z drog i,j oraz i,k+k,j
A[i,j].droga:=true;
end;
end;
//wypisanie wynikow
for i:=0 to n-1 do
begin
writeln;
for j:=0 to n-1 do
if A[i,j].droga=false then
write(' D['+IntToStr(i)+','+IntToStr(j)+']=niesk. ')
else
write(' D['+IntToStr(i)+','+IntToStr(j)+']='+FloatToStr(A[i,j].odl));
end;
readln;
end.