algorytm.org

Implementacja w Delphi/Pascal



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Floyda - Implementacja w Delphi/Pascal
Ocena użytkownikóww: *****  / 0
SłabyŚwietny
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.
Dodaj komentarz