Dijkstra: single source shortest path

Wiki: Dijkstra algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing.

topCoder: Dijstra via priority_queue

Dijkstra
In the last part of this tutorial I’ll describe how to efficiently implement Dijktra’s algorithm in sparse graph using STL containers. Please look through this tutorial for information on Dijkstra’s algoritm. Consider we have a weighted directed graph that is stored as vector< vector< pair<int,int> > > G, where

• G.size() is the number of vertices in our graph
• G[i].size() is the number of vertices directly reachable from vertex with index i
• G[i][j].first is the index of j-th vertex reachable from vertex i
• G[i][j].second is the length of the edge heading from vertex i to vertex G[i][j].first

We assume this, as defined in the following two code snippets:

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 

      vi D(N, 987654321); 
      // distance from start vertex to each vertex

      priority_queue<ii,vector<ii>, greater<ii> > Q; 
      // priority_queue with reverse comparison operator, 
      // so top() will return the least distance
      // initialize the start vertex, suppose it¡¯s zero
      D[0] = 0;
      Q.push(ii(0,0));

      // iterate while queue is not empty
      while(!Q.empty()) {

            // fetch the nearest element
            ii top = Q.top();
            Q.pop();
                        
            // v is vertex index, d is the distance
            int v = top.second, d = top.first;

            // this check is very important
            // we analyze each vertex only once
            // the other occurrences of it on queue (added earlier) 
            // will have greater distance
            if(d <= D[v]) {
                  // iterate through all outcoming edges from v
                  tr(G[v], it) {
                        int v2 = it->first, cost = it->second;
                        if(D[v2] > D[v] + cost) {
                              // update distance if possible
                              D[v2] = D[v] + cost;
                              // add the vertex to queue
                              Q.push(ii(D[v2], v2));

                        }
                  }
            }
      }

Problems: 

UVa 429 - Word Transformation