Dijkstra.cpp

#include "Graph.h"

#define MAXINT 1000

int printPath(int start, int end, vector<int> &parents, vector<int> &distance) {
  cout << end << " (" << distance[end] << "): ";

  int a = start;
  int b = end;

  while (a != b) {
    cout << b << " -> ";
    b = parents[b];
  }
  cout << start << endl;
}

void Dijkstra(Graph const &g, int start) {
  Node *tmp;
  vector<bool> inTree;
  vector<int>  distance;
  vector<int>  parent;
  int v, w;
  int weight;
  int dist;

  for (int i = 0; i <= g.vertices.size(); i++) {
    inTree.push_back(false);
    distance.push_back(MAXINT);
    parent.push_back(-1);
  }

  v = start;
  distance[v] = 0;

  // Run until there is no longer a vertex to pick.
  while (!inTree[v]) {
    inTree[v] = true;
    tmp = g.vertices[v];
    
    // Look at all neighbours of v.
    for (int i = 0; i < tmp->adjacencies.size(); i++) {
      w = tmp->adjacencies[i]->y;
      weight = tmp->adjacencies[i]->weight;

      // If the current distance to the successor vertex is greater than the
      // parent distance plus the weight of the edge, than change the distance
      // to it's shorter successor.
      if (distance[w] > (distance[v] + weight)) {
        distance[w] = distance[v] + weight;
        parent[w] = v;
      }
    }

    // Choose the shortest distance vertex.
    v = 1;
    dist = MAXINT;
    for (int x = 0; x < g.vertexIndices.size(); x++) {
      int i = g.vertexIndices[x];
      if (!inTree[i] && dist > distance[i]) {
        dist = distance[i];
        v = i;
      }
    }
  }

  for (int i = 0; i < g.vertexIndices.size(); i++) {
    w = g.vertexIndices[i];
    printPath(start, w, parent, distance);
  }
}

int main(int argc, char **argv) {
  Graph g(true);
  g.InsertEdge(0, 1, 6);
  g.InsertEdge(1, 4, 11);
  g.InsertEdge(0, 2, 8);
  g.InsertEdge(0, 3, 18);
  g.InsertEdge(4, 5, 3);
  g.InsertEdge(5, 2, 7);
  g.InsertEdge(5, 3, 4);
  g.InsertEdge(2, 3, 9);
  g.Print();

  cout << endl << "Running Dijkstra:" << endl;
  Dijkstra(g, 0);

  return 0;
}