Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
O(|V||E|) Djikstra
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment