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;
}
}
}
