program Graf;

const ZNAMY = 1;
const POKUSNY = 2;
const NEZNAMY = 3;

type Graf = object

   constructor vytvor( pocetUzlu : integer );

   function pocetUzlu() : integer;

   procedure vytvorHranu( uzel1, uzel2 : integer; vaha : real );

   function najdiSouseda( uzel, cisloSouseda : integer; var indexSouseda: integer; var vaha : real ) : boolean

end;

type NejkratsiCestaVGrafu = object

     procedure najdiNejkratsiCestu( var g : Graf, var cesta : array of integer );

     procedure inicializujUzly( var g: Graf );

     procedure nastavStavUzlu( indexUzlu, stav : integer );

     var stavyUzlu : array of integer;
     var hodnotyUzlu: array of real;
     var delkaCesta : integer;

end;

procedure NejkratsiCestaVGrafu.najdiNejkratsiCestu( var g : Graf, start, cil : integer, var cesta : array of integer )
var i, j: integer;
var minPokusny: integer;
var cisloSouseda, indexSouseda: integer;
var vaha: real;
begin
  inicializujUzly( g );
  oznacStart(start );
  najdiNejkratsiCesty( g, cil );
  rekonstruujCestu( g, cil, cesta );
end;

procedure NejkratsiCestaVGrafu.inicializujUzly( var g: Graf )
begin
  for i := 1 to g.pocetUzlu() do
    begin
      nastavStavUzlu( i, NEZNAMY );
      hodnotyUzlu[i] := REAL_MAX;
    end;
end

procedure NejkratsiCestaVGrafu.oznacStart( start : integer )
begin
  stavyUzlu[start] := POKUSNY;
  hodnotyUzlu[start] := 0;
end

procedure NejkratsiCestaVGrafu.najdiNejkratsiCesty( var g : Graf, cil : integer  )
begin
  while stavyUzlu[cil] <> ZNAMY do
  begin
    minPokusny := -1;
    for j := 1 to g.pocetUzlu() do
      begin
        if (stavyUzlu[j] = POKUSNY) and ((minPokusny = -1) or (hodnotyUzlu[j] < hodnotyUzlu[minPokusny]) then
          minPokusny := j;
      end;

    stavyUzlu[minPokusny] := ZNAMY;

    cisloSouseda := 1;
    while g.najdiSouseda(minPokusny, cisloSouseda, indexSouseda, vaha) <> false do
    begin
      if stavyUzlu[indexSouseda] <> ZNAMY then
        begin
          hodnotyUzlu[indexSouseda] := min(hodnotyUzlu[indexSouseda], hodnotyUzlu[minPokusny] + vaha);
          stavyUzlu[indexSouseda] := POKUSNY;
        end;

      cisloSouseda := cisloSouseda + 1;
    end;
  end;

end

procedure NejkratsiCestaVGrafu.rekonstruujCestu( var g : Graf, cesta : array of integer  )
begin
  cesta[1] := cil;
  i := 1;
  while cesta[i] <> start do
    begin
      cisloSouseda := 1;
      while g.najdiSouseda(cesta[i], cisloSouseda, indexSouseda, vaha) <> false do
      begin
        if hodnotyUzlu[cesta[i]] = hodnotyUzlu[indexSouseda] + vaha then
          begin
            i := i + 1;
            cesta[i] := indexSouseda;
            break;
          end;
      end;
    end;

    delkaCesty := i;
    for j := 1 to i / 2 do
      begin
        prohod(cesta[ i ], cesta[ j ]);
      end;
end

procedure NejkratsiCestaVGrafu.nastavStavUzlu( indexUzlu, stav : integer )
begin
     stavUzlu[ indexUzlu ] := stav;
end

function NejkratsiCestaVGrafu.nactiStavUzlu( indexUzlu : integer ) : integer
begin
     nactiStavUzlu : = stavUzlu[ indexUzlu ];
end