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