#include <float.h>

struct Graf
{
   Graf( int pocetVrcholu );  
   
   int pocetSousedu( const int vrchol );
   
   double vahaHranySouseda( const int vrchol, const int indexSouseda, int* sousedniVrchol );
   
   int pocetVrcholu;
   
   // sem by se hodila treba CSR matice (nebo spojovy seznam)
   
};


/****
 * Funkce vraci pocet vrcholu nejkratsi cesty a cestu uklada do pole
 * 'cesta'.
 */
int Dijkstra( const Graf g, int start, int cil, int* cesta )
{
   double* delkyCest = new double[ g.pocetVrcholu ];
   bool* pokusnyVrchol = new bool[g.pocetVrcholu];
   
   for( int i = 0; i < g.pocetVrcholu; i++ )
   {
      delkyCest[ i ] = DBL_MAX; // nekonecno
      pokusnyVrchol[ i ] = false;
   }
   delkyCest[ start ] = 0;
   
   int zafixovany = start;
   while (zafixovany != cil) {
      for (int i = 0; i < g.pocetSousedu(zafixovany);i++ ){
         int sousedniVrchol;
         double soucet = delkyCest [zafixovany]+ g.vahaHranySouseda(zafixovany,i,&sousedniVrchol);
         if( soucet < delkyCest[sousedniVrchol] )
         {
            delkyCest[ sousedniVrchol] = soucet;
            pokusnyVrchol[sousedniVrchol] = true;
         }
      }
      int nejmensiPokusny( -1 );
      for( int i = 0; i < g.pocetVrcholu; i++ )
      {
         if( pokusnyVrchol[ i ] )
         {
            if( nejmensiPokusny == - 1 )
               nejmensiPokusny = i;
            else
            {
               if( delkyCest[ i ] < delkyCest[ nejmensiPokusny])
                  nejmensiPokusny = i;
            }
         }
      }
      zafixovany = nejmensiPokusny;
      pokusnyVrchol[ zafixovany] = false;
   }
}