jeudi 5 mai 2016

Different output by adding a line of code

I am using Dijkstra's algorithm do find the minimum cost of a graph. When I run the code I get wrong output for some cases, but if I add a cout at a line then the output is correct. Can someone explain why that happens and how can I fix it.

double Dijkstra(vector< vector <pii> > adjList, int n, int source)
{
    vector<double> dist(n);
    //vector<int>prev(n);
    dist.clear();
    priority_queue < pii, vector<pii>, compare> Q;

    for(int i=0; i<n; i++)
    {
        dist[i] = numeric_limits<double>::max();
        //prev[i]=i;
    }
    dist[source]=1;
    bool in[n];
    Q.push(pii(source,dist[source]));
    in[source]= true;
    while(!Q.empty())
    {
        int u = Q.top().first;
        Q.pop();
        in[u]=false;
        for(unsigned  int i = 0; i < adjList[u].size(); ++i)
        {
            int v= adjList[u][i].first;
            double alt =  dist[u] * adjList[u][i].second;

            if(abs(dist[v]-alt)>0.000001 )
            {
                if(alt<dist[v])
                {
                    //if I add cout here
                    dist[v]=alt;
                    //prev[v]=u;
                    if(!in[v])
                    {
                      //if I add cout here
                        Q.push(pii(v,dist[v]));
                        in[v]=true;
                    }
                }

            }
            else
                jackpot = true;
        }
    }
    return dist[n-1];
}

Aucun commentaire:

Enregistrer un commentaire