Single Source Shortest Path (Dijkstra)

Single Source Shortest Path (Dijkstra)

   4:45 PM       Sayef Azad Sakin

---

 
struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};
int color[mx], d[mx], nodes;
vector < pii > path[MX];
int dijkstra(int source, int dest){
	int u,v,sz,y,z;
	priority_queue< pii, vector< pii >,comp > q;
	for(v = 1; v<=nodes; v++){
		color[v] = 0;
		d[v] = inf;
	}
	d[source] = 0;
	q.push(pii(source, 0));
	while(!q.empty()){
		u = q.top().first;
		if(u==dest)break;
		q.pop();
		if(color[u])continue;
		sz = path[u].size();
		for(v=0;v<sz;v++){
			y = path[u][v].first;
			z = path[u][v].second;
			if(!color[y] && d[u]+z < d[y]){
				d[y] = d[u]+z;
				q.push(pii(y,d[y]));
			}
		}
		color[u] = 1;
	}
	return d[dest];
}