Dijkstra

#include <algorithm>
#include <iostream>
#include <limits>
#include <list>
#include <queue>
#include <vector>
using namespace std;

//  Implementation of Dijkstra's algorithm, using the example graph from p596 of
//  Introduction to Algorithms. As STL's priority_queue does not contain a
//  decrease-key function, the vertex is simply added multiple times and only
//  the lowest distance (first encountered on queue) is considered. Note that 
//  the number of nodes in the graph is fixed to keep code simple.

typedef pair<int,int> pii;

const int max_nodes = 5;
int distances[max_nodes];
bool visited[max_nodes];

void Dijkstra(list<pii> Adj[max_nodes], int s)
{
    for(int i=0;i<max_nodes;++i)
    {
        distances[i] = numeric_limits<int>::max();
        visited[i] = false;
    }
    distances[s] = 0;

    priority_queue<pii, vector<pii>, greater<pii> > Q;// pair(distance, vertex)
    Q.push(make_pair(distances[s],s));

    while(!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();

        // If the vertex has been visited (by a shorter path) while it was in
        // the queue ignore it.
        if(visited[u]) continue;
        visited[u]=true;

        // Relax each adjacent vertex that hasn't already been visisted. If it
        // has been visited it will have been by a shorter path.
        for(list<pii>::iterator v=Adj[u].begin(); v != Adj[u].end(); ++v)
        {
            // If d(s,u) + d(u,v) < d(s,v) update d(s,v).
            if(!visited[v->first] && distances[v->first] > distances[u] + v->second)
            {
                distances[v->first] = distances[u] + v->second;
                Q.push(make_pair(distances[v->first],v->first));
            }
        }
    }
}

int main()
{
    list<pii> Adj[max_nodes];
    Adj[0].push_back(make_pair(1,10));    // (s,t)
    Adj[0].push_back(make_pair(3,5));    // (s,y)
    Adj[1].push_back(make_pair(2,1));    // (t,x)
    Adj[1].push_back(make_pair(3,2));    // (t,y)
    Adj[2].push_back(make_pair(4,4));    // (x,z)
    Adj[3].push_back(make_pair(1,3));    // (y,t)
    Adj[3].push_back(make_pair(2,9));    // (y,x)
    Adj[3].push_back(make_pair(4,2));    // (y,z)
    Adj[4].push_back(make_pair(0,7));    // (z,s)
    Adj[4].push_back(make_pair(2,6));    // (z,x)

    Dijkstra(Adj, 0);

    for(int i=0;i<max_nodes;++i)
    {
        cout << "distances["<<i<<"] = " << distances[i] << ".\n";
    }
}