2014/3/5: How stupid I was for not recognizing Dijkstra as a special case of A* without heuristic cost. It makes the algorithm much easier to understand and implement. We only need to consider vertices as states and put them to a priority_queue.

Furthermore, I did not know that we need to implement Dijkstra’s differently in case of dense graph. The below code runs in O(E log(V))~O(V^2 log(V)) in dense graph. However, there is another implementation with O(V^2) complexity.

Let s be the source and (S,V-S) is a cut of graph G. The pseudo code

for v in V: distance[v]=INFINITY S={s} distance[s]=0; while(S!=V){ u:= argmin distance[u] for u in (V-S) for v adjacent to u: if(u in (V-S) && distance[u]+weight(u,v)<distance[v]) distance[v]=distance[u]+weight(u,v) S=S+{u} }

If we can determine if a vertex u in (V-S) in O(1) time, then the above code will run in O(V^2) time as there are V iterations in each one of V loops. This can be done by an bool array. This method is easier to understand than the below code.

2014/03/03: I have heard and read about single source shortest path problem in graph theory dozens of time, but it’s the first time I have ever actually write a program to solve it. The algorithm follows greedy paradigm to update the shortest distance from source to each of every other vertices.

The dijkstra function is quite simple as follows

#define INF numeric_limits<int>::max() vector<int> shortestPath(Graph &g, int start=1){ vector<int> parent(g.V(),-1); vector<double> distance(g.V(),INF); vector<bool> done(g.V(), false); parent[start]=start; distance[start]=0; MinPQ pq; pq.init(g.V()); pq.push(Pair(0.0,start)); while(!pq.empty()){ Pair curr = pq.pop(); if(done[curr.second]) continue; done[curr.second]=true; for(auto e:g.adj[curr.second]){ if(done[e.to()]) continue; double dis = e.weight+distance[e.from()]; if(dis<distance[e.to()]){ int index=pq.find(e.to()); if(index==-1) pq.push(Pair(dis,e.to())); else pq.decrease(Pair(dis,e.to()), index); parent[e.to()]=e.from(); distance[e.to()]=dis; } } } return parent; }

The most important and difficult part is to build MinPQ. Default priority_queue in C++ does not support find and decrease methods, which are vital to dijkstra’s algorithm. At first I implement find in O(V) time, it works but not so efficient. I then use an additional array mapindex to hold the index of vertices in MinPQ, which makes both find and decrease O(1) operations.

class MinPQ{ private: Pair *data; int* mapindex; int MAX; int size; public: MinPQ():size(0),MAX(0),data(NULL),mapindex(NULL){ } ~MinPQ(){ delete[] data; delete[] mapindex; } void init(int max){ if(data) delete[] data; if(mapindex) delete[] mapindex; MAX=max; size=0; data=new Pair[max]; mapindex= new int[max]; for(int i=0; i<max; i++) mapindex[i]=-1; } void heapify_up(int child){ int parent=child/2; while(parent && data[child].first<data[parent].first){ swap(data[child],data[parent]); updateindex(child); updateindex(parent); child=parent; parent/=2; } } void heapify_down(int parent){ int child=2*parent; while(child<=size){ if(child<size-1 && data[child+1].first<data[child].first) child++; if(data[child].first<data[parent].first){ swap(data[child], data[parent]); updateindex(child); updateindex(parent); parent=child; child*=2; } else break; } } void updateindex(int index){ mapindex[data[index].second]=index; } bool push(const Pair& x){ if(size>=MAX) return false; data[++size]=x; updateindex(size); heapify_up(size); return true; } Pair min() const{ assert(!empty()); return data[1]; } Pair pop(){ assert(!empty()); Pair value = data[1]; data[1]=data[size--]; updateindex(1); heapify_down(1); mapindex[value.second]=-1; return value; } bool empty() const{ return size==0; } int find(int id){ return mapindex[id]; } bool decrease(const Pair& t, int index){ data[index]=t; heapify_up(index); } };

Time complexity is O(E logV) and space complexity is O(V).

Tested on data from this website. http://algs4.cs.princeton.edu/44sp/

References

Algorithms, Robert Sedgewick