#include <iostream.h>

#define MAX 100    // maximum number of vertices
#define INF 10000  // must be bigger than any shortest-path

class vertex {
public:
  int adj[MAX];       // vertices adjacent to this one
  int nadj;           // # of vertices adjacent to this one
  double wadj[MAX];   // weights of vertices adjacent to this one

  // these fields are undefined until dijkstra() is called
  int pred;           // previous hop on path from source to here
  double cost;        // cost to get here from source

  vertex() { nadj = 0; }
  void push(int neighbor, double cost) {
    adj[nadj] = neighbor;
    wadj[nadj] = cost;
    nadj++;
  }
};

// find shortest paths from source to all other nodes
// variations on this function are possible: returning the entire cost
// array, taking a dest argument and returning cost[dest], etc.  this
// variation fills in the 'pred' field and 'cost' of each node so
// that path and cost cost can be determined trivially after
// dijkstra returns.
void dijkstra(vertex *v, int size, int source) {
  double cost[MAX];
  int done[MAX];
  int to_do = size;
  int i;
  for (i=0; i<size; i++) {
    v[i].cost = cost[i] = INF; v[i].pred = -1; done[i] = 0;
  }
  cost[source] = 0;
  while (to_do) {
    int mini;
    for (i=0; i<size; i++) if (!done[i]) { mini=i; break; }
    for (i=mini+1; i<size; i++)
      if (!done[i] && cost[i] < cost[mini]) mini = i; 
    done[mini] = 1;
    to_do--;
    for (i=0; i<v[mini].nadj; i++)
      if (cost[mini] + v[mini].wadj[i] < cost[v[mini].adj[i]]) {
        v[v[mini].adj[i]].pred = mini;
        v[v[mini].adj[i]].cost = cost[v[mini].adj[i]] =
          cost[mini] + v[mini].wadj[i];
      }
  }
}

// print the path from source to dest
// important: you must have already called dijkstra(..., source)
void print_path(vertex *v, int source, int dest, char *sep) {
  if (source == dest)
    cout << dest;
  else {
    print_path(v, source, v[dest].pred, sep);
    cout << sep << dest;
  }
}

// some examples
int main() {
  vertex v[MAX];

  // ... make up a graph (from CLR p.528)
  v[0].push(1, 10.0);
  v[0].push(3, 5.0);
  v[1].push(2, 1.0);
  v[1].push(3, 2.0);
  v[2].push(4, 4.0);
  v[3].push(1, 3.0);
  v[3].push(2, 9.0);
  v[3].push(4, 2.0);
  v[4].push(0, 7.0);
  v[4].push(2, 6.0);

  dijkstra(v, 5, 0);          // calculate paths from 0->everywhere
  print_path(v, 0, 1, ", ");  // print path from 0->1 (0 3 1)
  cout << endl;
  print_path(v, 0, 2, ", ");  // print path from 0->2 (0 3 1 2)
  cout << endl;
  cout << v[4].cost << endl;  // print cost of path from 0->4 (7.0)

  //print_path(v, 2, 4, ", ");// INVALID!  You must call dijkstra(..., 2) first
}