Find single-source shortest paths: Dijkstra algorithm implementation

A generic shortest path algorithm to find shortest path from single source vertex for graph is as following:

Given Graph(V, E, W), V is the set of vertices, E is the set of edges, W is the set of weights for each edge, and source vertex s.

distance[] array contains the distance from any vertex to source vertex s
parent[] array contains the previous vertex to any vertex on a given shortest path

1. initialize
 for any v:
  d[v] = infinity, parent[v] = null
d[s] = 0

2. relaxation
flag = true
while(flag)
 flag = false
 for any edge u, v
   if(d[v] > d[u] + w(u, v)){
    d[v] = d[u] + w(u, v)
    parent[v] = u
    flag = true
   }


Couple optimized shortest path algorithm exists to implement different ways of relaxation and make d[] converge fast. Dijkstra algorithm is one of them. It can handle any graph even with cycles, but all of the weights have to be non-negative.

public class ShortestPathQ {

/*

* Dijkstra algorithm for any graph with positive weights

* the algorithm essentially is BFS using a priority queue

*/

/*

* here i assume graph is represented as adjacent matrix, D

* vertex is represented as number of 0, 1, ..., n-1

* the value at each cell D[i][j] represent weight of the edge

* from vertex i to j

*/

//a custom PQ to hold the list of vertex ordered by their distances from source

class PQ {

//the binary heap represented as array

int[] heap;

//keep track of vertex position in the heap

int[] indices;

int[] distance;

int size;

//time complexity O(size)

PQ(int s, int[] d){

size = s;

heap = new int[s];

distance = d;

heapify();

}

//time complexity O(size)

void heapify(){

for(int i = 0; i<size; i++){

heap[i] = i;

indices[i] = i;

}

for(int i=size/2; i>=0; i--)

bubbleDown(i);

}

//time complexity O(lg(size))

void bubbleDown(int index){

int target = index;

int left = index*2+1;

if(left<size && distance[left] < distance[target])

target = left;

int right = index*2+1;

if(right<size && distance[right] < distance[target])

target = right;

if(target!=index){

swap(target, index);

bubbleDown(target);

}

}

void swap(int i, int j){

int tem = heap[i];

heap[i] = heap[j];

heap[j] = tem;

tem = indices[i];

indices[i] = indices[j];

indices[j] = tem;

}

//time complexity O(lg(size))

void bubbleUp(int index){

int target = index;

int parent = (index-1)/2;

if(parent>=0 && distance[parent] > distance[target])

target = parent;

if(target!=index){

swap(target, index);

bubbleUp(target);

}

}

int min(){

return heap[0];

}

//time complexity O(lg(size))

int removeMin(){

int i = heap[0];

heap[0] = heap[--size];

bubbleDown(0);

return i;

}

int indexOf(int vertex){

return indices[vertex];

}

boolean isEmpty(){

return size == 0;

}

}

class Graph {

int[][] w;

int size;

Graph(int size){

this.size = size;

w = new int[size][size]; 

}

/*

* undirected graph representation

* weight zero means no edge between two vertex

*/

void addEdge(int i, int j, int we){

w[i][j] = we;

w[j][i] = we;

}

/* given vertex, dijkstra algorithm will calculate 

* shortest path from it to any vertex in the graph 

*/

int[] dijkstra(int source){

  int[] distance;

int[] parent;

//initialize

distance = new int[this.size];

parent = new int[this.size];

for(int i=0;i<this.size; i++){

distance[i] = Integer.MAX_VALUE;

parent[i] = -1;

}

distance[source] = 0;

parent[source] = -1;

PQ queue = new PQ(this.size, distance);

while(!queue.isEmpty()){

int u = queue.removeMin();

for(int v = 0; v < size; v++){

if(w[u][v] != 0){//there is edge from u to v

//relaxation O(lgsize)

if(distance[v] > distance[u] + w[u][v]){

distance[v] = distance[u] + w[u][v];

parent[v] = u;

queue.bubbleUp(queue.indexOf(v));

}

}

}

}  

return distance;

}



//PQ implemented in java PriorityQueue but it doesn't have optimized update() or remove()
// method, time complexity is O(size) at relaxation step
int[] dijkstraUsingJavaPQ(int source){
final int[] distance;
int[] parent;

//initialize

distance = new int[this.size];
parent = new int[this.size];
for(int i=0;i<this.size; i++){
distance[i] = Integer.MAX_VALUE;
parent[i] = -1;
}

distance[source] = 0;
parent[source] = -1;

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(this.size, new Comparator<Integer>(){

@Override

public int compare(Integer i, Integer j){
if(distance[i] == distance[j])
return 0;
else if(distance[i] > distance[j])
return 1;
else
return -1;
}
});

for(int i = 0; i<size; i++)
queue.add(i);

while(!queue.isEmpty()){
int u = queue.remove();
for(int v = 0; v < size; v++){

if(w[u][v] != 0){//there is edge from u to v

//relaxation O(size)

if(distance[v] > distance[u] + w[u][v]){
distance[v] = distance[u] + w[u][v];
parent[v] = u;
queue.remove(v);//remove by equals()
queue.add(v);
}
}
}
}

return distance;
}

}

}