Doubt in Dijkstra!

1

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[505];
    vector<edge> adj[505];

    void Dijkstra(){
    	for( int i=2; i<=n; ++i ) path[i] = INF;
    	path[1] = 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]) );
    			}
    		}
    	}
    }
2

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
3

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.