1: #include <iostream.h>
    2: 
    3: #define MAX 100    // maximum number of vertices
    4: #define INF 10000  // must be bigger than any shortest-path
    5: 
    6: class vertex {
    7: public:
    8:   int adj[MAX];       // vertices adjacent to this one
    9:   int nadj;           // # of vertices adjacent to this one
   10:   double wadj[MAX];   // weights of vertices adjacent to this one
   11: 
   12:   // these fields are undefined until dijkstra() is called
   13:   int pred;           // previous hop on path from source to here
   14:   double cost;        // cost to get here from source
   15: 
   16:   vertex() { nadj = 0; }
   17:   void push(int neighbor, double cost) {
   18:     adj[nadj] = neighbor;
   19:     wadj[nadj] = cost;
   20:     nadj++;
   21:   }
   22: };
   23: 
   24: // find shortest paths from source to all other nodes
   25: // variations on this function are possible: returning the entire cost
   26: // array, taking a dest argument and returning cost[dest], etc.  this
   27: // variation fills in the 'pred' field and 'cost' of each node so
   28: // that path and cost cost can be determined trivially after
   29: // dijkstra returns.
   30: void dijkstra(vertex *v, int size, int source) {
   31:   double cost[MAX];
   32:   int done[MAX];
   33:   int to_do = size;
   34:   int i;
   35:   for (i=0; i<size; i++) {
   36:     v[i].cost = cost[i] = INF; v[i].pred = -1; done[i] = 0;
   37:   }
   38:   cost[source] = 0;
   39:   while (to_do) {
   40:     int mini;
   41:     for (i=0; i<size; i++) if (!done[i]) { mini=i; break; }
   42:     for (i=mini+1; i<size; i++)
   43:       if (!done[i] && cost[i] < cost[mini]) mini = i; 
   44:     done[mini] = 1;
   45:     to_do--;
   46:     for (i=0; i<v[mini].nadj; i++)
   47:       if (cost[mini] + v[mini].wadj[i] < cost[v[mini].adj[i]]) {
   48:         v[v[mini].adj[i]].pred = mini;
   49:         v[v[mini].adj[i]].cost = cost[v[mini].adj[i]] =
   50:           cost[mini] + v[mini].wadj[i];
   51:       }
   52:   }
   53: }
   54: 
   55: // print the path from source to dest
   56: // important: you must have already called dijkstra(..., source)
   57: void print_path(vertex *v, int source, int dest, char *sep) {
   58:   if (source == dest)
   59:     cout << dest;
   60:   else {
   61:     print_path(v, source, v[dest].pred, sep);
   62:     cout << sep << dest;
   63:   }
   64: }
   65: 
   66: // some examples
   67: int main() {
   68:   vertex v[MAX];
   69: 
   70:   // ... make up a graph (from CLR p.528)
   71:   v[0].push(1, 10.0);
   72:   v[0].push(3, 5.0);
   73:   v[1].push(2, 1.0);
   74:   v[1].push(3, 2.0);
   75:   v[2].push(4, 4.0);
   76:   v[3].push(1, 3.0);
   77:   v[3].push(2, 9.0);
   78:   v[3].push(4, 2.0);
   79:   v[4].push(0, 7.0);
   80:   v[4].push(2, 6.0);
   81: 
   82:   dijkstra(v, 5, 0);          // calculate paths from 0->everywhere
   83:   print_path(v, 0, 1, ", ");  // print path from 0->1 (0 3 1)
   84:   cout << endl;
   85:   print_path(v, 0, 2, ", ");  // print path from 0->2 (0 3 1 2)
   86:   cout << endl;
   87:   cout << v[4].cost << endl;  // print cost of path from 0->4 (7.0)
   88: 
   89:   //print_path(v, 2, 4, ", ");// INVALID!  You must call dijkstra(..., 2) first
   90: }