How to implement Dijkstra's algorithm

Dijkstra's algorithm is a graph search algorithm, often used in routing. For a given node in the graph, the algorithm finds the path with lowest cost between that node and every other node. It can also be used for finding costs of shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path (lowest cost) to the destination node has been determined.

The algorithm is described on-line fairly good, so I won't spend time describing it again here. The main ideas are that we need to keep a list with all the nodes that we visited and another list with all the nodes that we still haven't visited. At each iteration we take the unvisited node with the lowest distance from the source (calculated so far) and calculate the distance from the source to each of it's neighbors. We stop when there are no unvisited nodes.

I'm just going to print the algorithm since it does all the talking by itself. Some comments are available in the code which should explain everything.

   1:  #include <iostream>

   2:  #include <vector>

   3:  #include <string>

   4:  #include <set>

   5:  #include <queue>

   6:  using namespace std;

   7:   

   8:  const int SIZE = 5; //number of nodes

   9:  int graph[SIZE][SIZE];//the graph itself

  10:  int d[SIZE]; //distances from the source to each node

  11:  int pi[SIZE];//contains the predecessor node for each node

  12:  vector<int> s;//list of nodes which were already visited

  13:  vector<int> vs;//list of nodes which were not visited yet

  14:   

  15:  void sort(vector<int>* vec) {

  16:      //sorts the vector of nodes according to 

  17:      //distances from the source to each node

  18:      for (unsigned int i = 0; i < vec->size(); i++)

  19:          for (unsigned int j = i; j < vec->size(); j++)

  20:              if (d[vec->at(i)] > d[vec->at(j)]) {

  21:                  int temp = vec->at(i);

  22:                  vec->at(i) = vec->at(j);

  23:                  vec->at(j) = temp;

  24:              }

  25:  }

  26:   

  27:  void relax(vector<int>* vec, int u) {

  28:      //updates the distances from the source to each node

  29:      //and the predecessor for each node

  30:      for (unsigned int i = 0; i < vec->size(); i++) {

  31:          int vi = vec->at(i);

  32:          if (graph[u][vi] == SHRT_MAX)

  33:              continue;

  34:          if (d[vi] > d[u] + graph[u][vi]) {

  35:              d[vi] = d[u] + graph[u][vi];

  36:              pi[vi] = u;

  37:          }

  38:      }

  39:  }

  40:   

  41:  void printShortestPathTo(int v) {

  42:      //this simply prints the vector of predecessors

  43:      //for the requested node (v)

  44:      cout << "Distance to " << v << " is " << d[v] << endl;

  45:      cout << "Shortest path: ";

  46:      int x = pi[v];

  47:      while (x != -1) {

  48:          cout << x << "<-";

  49:          x = pi[x];

  50:      }

  51:      cout << endl << endl;

  52:  }

  53:   

  54:  int main() {

  55:      //initialize all the costs in the graph

  56:      for (int i = 0; i < SIZE; i++)

  57:          for (int j = 0; j < SIZE; j++)

  58:              graph[i][j] = SHRT_MAX;

  59:   

  60:      graph[0][1] = 20;

  61:      graph[0][4] = 40;

  62:      graph[1][4] = 50;

  63:      graph[2][3] = 30;

  64:      graph[2][4] = 60;

  65:      graph[4][2] = 20;

  66:      graph[4][3] = 100;

  67:   

  68:      for (int i = 0; i < SIZE; i++) {

  69:          for (int j = 0; j < SIZE; j++) {

  70:              cout << graph[i][j] << "\t";

  71:          }

  72:          cout << endl;

  73:      }

  74:      for (int i = 0; i < SIZE; i++) {

  75:          vs.push_back(i);//initialize all the variables

  76:          d[i] = SHRT_MAX;//all distances to infinite

  77:          pi[i] = -1;//nodes have no predecesors 

  78:      }

  79:      d[0] = 0; //the distance of the source is 0

  80:      sort(&vs); //we sort the nodes according to the distance

  81:   

  82:      while (vs.size() > 0) {

  83:          int x = vs.front();//take the node with the shortest distance

  84:          for (unsigned int i = 0; i < vs.size() - 1; i++) {

  85:              vs.at(i) = vs.at(i + 1);

  86:          }

  87:          vs.pop_back();

  88:          s.push_back(x);//mark it as visited

  89:          relax(&vs, x);//update the distances

  90:          sort(&vs); //sort the nodes according to the new distances

  91:      }

  92:   

  93:      printShortestPathTo(4);//choose any node

  94:      return 0;

  95:  }