O(|V||E|) Djikstra

djikstra-slow.cpp

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

struct Edge {
  int src, dst;
  int w;
};

class Graph {
 public:
  Graph(int V);
  void addEdge(int src, int dst, int w);
  vector<int> djikstra(int src);

 public:
  static const int INF = 1e9;
  
 private:
  static int closestVertex(vector<int> &dist, vector<bool> &visited);

 private:
  int V;
  // I am keeping the edges in the vector itself.
  // We can keep a map<vertex-id, edge>. There is an
  // O(log N) look-up cost, where N is the number of
  // vertices in the map. But if the graph is sparse,
  // (which is when we use adjacency lists), this is
  // pretty small.
  vector<Edge> *adj;
};

Graph::Graph(int V) {
  assert(V > 0);
  this->V = V;
  this->adj = new vector<Edge>[V];
}

void Graph::addEdge(int src, int dst, int w) {
  // Doing some error checking here. In real interviews,
  // one can skip all this error checks. Just make sure
  // you mention this to the interviewer.
  assert(src < V && src >= 0);
  assert(dst < V && dst >= 0);
  assert(w > 0);
  assert(src != dst);

  // Also check that an edge has not already been inserted
  // to the dst. If this was a map, we would over-write.
  for (int i = 0; i < adj[src].size(); i++) {
    assert(adj[src][i].dst != dst);
  }
 
  Edge e;
  e.src = src;
  e.dst = dst;
  e.w = w;
  adj[src].push_back(e);
}


int Graph::closestVertex(vector<int> &dist, vector<bool> &visited) {
  int ret = -1, val = Graph::INF;
  for (int i = 0; i < dist.size(); i++) {
    if (!visited[i] && val > dist[i]) {
      ret = i;
      val = dist[i];
    }
  }
  return ret;
}

vector<int> Graph::djikstra(int src) {
  assert(src >= 0 && src < V);
  
  // Create a vector and initialize to INF.
  vector<int> dist(V, Graph::INF);
  vector<bool> visited(V, false);
  dist[src] = 0;
  
  int u = closestVertex(dist, visited);
  while (u != -1) {
    cerr << "Chose vertex " << u << ", with distance: " << dist[u] << endl;
    visited[u] = true;

    for (int i = 0; i < adj[u].size(); i++) {
      Edge e = adj[u][i];
      dist[e.dst] = min(dist[e.dst], dist[u] + e.w);
    }
    u = closestVertex(dist, visited);
  }
  for (int i = 0; i < dist.size(); i++) {
    cerr << dist[i] << " ";
  }
  cerr << endl;
  return dist;
}

int main() {
  Graph g(5);
  g.addEdge(0, 1, 4);
  g.addEdge(0, 2, 3);
  g.addEdge(2, 3, 1);
  g.addEdge(1, 3, 10);
  g.djikstra(0);
}