{ Ukazkovy program na hledani nejkratsi cesty pomoci Floyd-Warshallova algoritmu  }
{ Program obsahuje ukazkovy graf z webu (uloha se 4 mesty) }
{ Z webu http://teorie-grafu.elfineer.cz, Bc. prace z MFF UK, Lukas Jirovsky }
program GRAFMATICE1;

const
  velikost_matice = 4;

type
  typ_matice = array[1..velikost_matice,1..velikost_matice] of integer;

var
  matice1: typ_matice;

procedure vycistiMatici(var matice:typ_matice);
var
  i, j: integer;
begin
  for i:=1 to velikost_matice do
    begin
    for j:= 1 to velikost_matice do
      begin
      matice[i,j]:= 999;
      end;
    end;
end;

procedure zadejHranu(odkud: integer; kam: integer; vzdalenost: integer; var matice:typ_matice);
begin
  matice[odkud,kam]:= vzdalenost;
  matice[kam,odkud]:= vzdalenost;
end;

procedure odeberHranu(odkud: integer; kam: integer; var matice:typ_matice);
begin
  matice[odkud,kam]:= 0;
  matice[kam,odkud]:= 0;
end;

function jeHrana(odkud: integer; kam: integer; var matice:typ_matice):boolean;
begin
  if(matice[odkud,kam] = 1) then jeHrana:=true else
                                 jeHrana:=false;
end;

function minimum(a: integer; b: integer):integer;
begin
  if(a<=b) then minimum:= a else
  minimum:= b;

end;

procedure nejkratsiCesta(var matice:typ_matice);
{ Samotne hledani nejkratsi cesty }
var
 i, j, k: integer;
 {pomocne promenne}
begin
  for i:=1 to velikost_matice do
    begin
    for j:=1 to velikost_matice do
      begin
      for k:=1 to velikost_matice do
        begin
        matice[i,j]:= minimum(matice[i,j], (matice[i,k] + matice[k,j]));
        end; { k }
      end; { j }
    end; { i }
end;

procedure vypisMatici(var matice:typ_matice);
var
   i,j: integer;
begin
   writeln('Matice:');
   for i:=1 to velikost_matice do
    begin
     for j:= 1 to velikost_matice do
      begin
      write(matice[i,j]);
      write(',');
      end;
     writeln;
    end;
    writeln('--->KONEC MATICE---->');
    writeln;
end;

begin
  {samotny program}
  vycistiMatici(Matice1);
  vypisMatici(Matice1);

  {zadani nekolika testovacich hran}
  zadejHranu(1,2,63,Matice1);
  zadejHranu(1,3,103,Matice1); 
  zadejHranu(1,4,157,Matice1);
  zadejHranu(3,4,69,Matice1);
  zadejHranu(2,4,111,Matice1);
  zadejHranu(2,3,33,Matice1);
  { Most   ..1
    Kladno ..2
    Praha  ..3
    Kolin  ..4 }

  vypisMatici(Matice1);
  nejkratsiCesta(Matice1);
  vypisMatici(Matice1);
  readln;
end.