Ronzii's Blog

Just your average geek's blog

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;
}
Advertisements

July 7, 2011 - Posted by | C++ | , , , ,

2 Comments »

  1. Yep, it works. Thanks allot.

    Comment by Anonymous | August 20, 2011 | Reply

  2. nice!

    Comment by me | August 28, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s