## Dijkstra’s algorithm using STL

Dijkstra’s algorithm requires a priority queue so I have used STL’s inbuilt priority queue functions. The class Prioritize ensures that the queue remains sorted according to the first value of the pair<int,int> object

**Algorithm**

1. Assign to every node a distance value: set it to zero for our initial node and to infinity(999) for all other nodes. Mark all nodes as unvisited.

2. Set initial source as current.

3. Consider all its unvisited neighbors and calculate their distance. For example, if current node (A) has distance of 1, and an edge connecting it with another node (B) is 2, the distance to B through A will be 1+2=3

4.When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal

5. The next *current node* will be the node with the lowest distance in the *unvisited set *that is the topmost element of the priority queue.

#include<iostream> #include<cstdio> #include<vector> #include<queue> #define pp pair<int,int> using namespace std; class Prioritize { public: int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 ) { return p1.second < p2.second; } }; int main() { priority_queue<pp, vector<pp > , Prioritize > Q; int n; cin>>n; vector< pp > G[n+1]; int e,u,v,w; cin>>e; for(int i=0;i<e;i++) { cin>>u>>v>>w; G[u].push_back(pp(v,w)); G[v].push_back(pp(u,w)); } int s; cin>>s; int d[n+1]; for(int i=1;i<=n;i++) { d[i] = 999; } d[s] = 0; Q.push(pp(s,d[s])); while(!Q.empty()) { u = Q.top().first; Q.pop(); int size = G[u].size(); for(int i = 0 ; i < size ; i++) { v = G[u][i].first; w = G[u][i].second; cout<<u<<" "<<v<<" "<<w<<endl; if(d[v] > d[u] + w) { d[v] = d[u] + w; Q.push(pp(v,d[v])); } } } for(int i=1; i<=n; i++) printf("Node %d, min weight = %d\n", i, d[i]); return 0; }

Yep, it works. Thanks allot.

Comment by Anonymous | August 20, 2011 |

nice!

Comment by me | August 28, 2012 |