#include "graf.h"

//////
// Vraci pocet vrcholu, pres ktere vede nejkratsi cesta
// Posloupnost vrcholu je v poli cesta
int Dijkstra( Graf graf,
              int start,
              int cil,
              int* cesta )
{
    int N = graf.pocetVrcholu();
    bool* zname = new bool[ N ];
    double* delkyCest = new double[ N ];
    
    for( int i = 0; i  < N; i++ )
    {
        zname[ i ] = false;
        delkyCest[ i ] = DBL_MAX; // nejvetsi mozna hodnota pro typ double
    }
    delkyCest[ start ] = 0.0;
    Halda pokusne;
    pokusne.vloz( start, delkyCest );
    
    while(zname[cil]!=true)
    {
        int nejmensi = pokusne.vratNejmensi();
        zname[nejmensi]=true;
        for (int hrana=0; hrana < graf.pocetSousedu(nejmensi);hrana++)
        {
            int soused = graf.soused(nejmensi,hrana);
            if( zname[ soused ] == true )
                continue;
            double p = delkyCest[nejmensi]+graf.delkaHrany(nejmensi, hrana);
            if (p<delkyCest[soused])
            {
                if(delkyCest[soused]==DBL_MAX)
                   pokusne.vloz(soused, delkyCest);
                else 
                   pokusne.prepocitej(soused,delkyCest);
            }
        }
    }
    // Rekonstrukce cesty
    int vrchol=cil;
    cesta[0]=cil;
    int index=1;    
    while(vrchol != start)
    {
        for (int hrana=0; hrana < graf.pocetSousedu(vrchol);hrana++)
        {
            int soused = graf.soused(vrchol,hrana);
            double p = delkyCest[vrchol]-graf.delkaHrany(vrchol, hrana);
            if (p==delkyCest[soused])
            {
                vrchol=soused;
                cesta[index]=vrchol;
                index++;
                break;
            }
        }
    }
    int i=0;
    int j=index-1;
    while(i<j)
    {
        int pom;
        pom=cesta[j];
        cesta[j]=cesta[i];
        cesta[i]=pom;
        i++;
        j--;
    }
    return index;
}