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