 # Doubt in Dijkstra!

Please see below code for dijkstra algorithm and tell me is it perfectly correct!

``````    typedef pair<int, int> edge;

int n, m, tc, a, b, c;
double ans;
int path;
vector<edge> adj;

void Dijkstra(){
for( int i=2; i<=n; ++i ) path[i] = INF;
path = 0;
priority_queue<edge> pq;
pq.push( edge(1, 0) );   //here, edge is a pair whose first element is vertex number and second element is weight of edge
while( !pq.empty() ){
int u = pq.top().first;
int W = pq.top().second;
pq.pop();
if( path[u] != W ) continue;
for( int i=0; i<adj[u].size(); ++i ){
int v = adj[u][i].first;
int w = adj[u][i].second;
if( path[v] > W + w ){
path[v] = W + w;
pq.push( edge(v, path[v]) );
}
}
}
}
``````

Here, i think the edge first element should be weight, right? But it works the other way round also.
And also please explain the significance of this line :

1 Like

There is an inaccuracy. The way you are storing edges ( <edge_number, edge weight> ) when you push this into the priority queue, it will pop edges in the increasing order of edge number, why ? because it sorts pairs based on lower first element and then lower second element if first elements are equal.