## Sunday, November 29, 2015

### Dijkstra's Algorithm using Fibonacci Heap Priority Queue implementation : Java

This code uses Fibonacci heap for the priority queue used which is faster than other priority queue implementations (binary heap, d-way heap or linear).

Fibonacci Heap source : graphstream-project.org

Code:

```import java.util.ArrayList;
import java.util.Arrays;
import org.graphstream.algorithm.util.FibonacciHeap;

public class Dijkstras {
class Edge{
int to, from;
double weight;

Edge(int from, int to, double weight){
this.to = to;
this.from = from;
this.weight = weight;
}

public String toString(){
return "["+from+", "+to+" : "+weight+"]";
}
}

private ArrayList<ArrayList<Edge>> graph;
private int edgeTo[];
private double distTo[];
private boolean inQ[];
private FibonacciHeap.Node nodeRef[];
private int V;

FibonacciHeap<Double, Integer> pq;

Dijkstras(int V){
graph = new ArrayList<>();
graph.ensureCapacity(V);
edgeTo = new int[V];
distTo = new double[V];
this.V = V;
}

public void addEdge(int from, int to, double weight){
}

public void runDijkstra(int s){
pq = new FibonacciHeap<>();
inQ = new boolean[V];
nodeRef = new FibonacciHeap.Node[V];

Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[s] = 0;

inQ[s] = true;

while(!pq.isEmpty()){
int v = pq.extractMin();
for(Edge e : graph.get(v)){
relax(e);
}
}
}

public void relax(Edge e){
if(!inQ[e.to]){
distTo[e.to] = distTo[e.from]+e.weight;
inQ[e.to] = true;
edgeTo[e.to] = e.from;
}else if(distTo[e.to] > distTo[e.from] + e.weight){
distTo[e.to] = distTo[e.from] + e.weight;
edgeTo[e.to] = e.from;
pq.decreaseKey(nodeRef[e.to], distTo[e.to]);
}
}

public static void main(String[] args){
Dijkstras d = new Dijkstras(8);

d.runDijkstra(0);

System.out.println("Results: ");
for(int i=0;i<d.V;++i){
System.out.println("Vertex "+i+" edgeTo["+i+"] = "+d.edgeTo[i]+" distTo["+i+"] = "+d.distTo[i]);
}
}

}```

Output:

Results:
Vertex 0 edgeTo[0] = 0 distTo[0] = 0.0
Vertex 1 edgeTo[1] = 0 distTo[1] = 5.0
Vertex 2 edgeTo[2] = 5 distTo[2] = 14.0
Vertex 3 edgeTo[3] = 2 distTo[3] = 17.0
Vertex 4 edgeTo[4] = 0 distTo[4] = 9.0
Vertex 5 edgeTo[5] = 4 distTo[5] = 13.0
Vertex 6 edgeTo[6] = 2 distTo[6] = 25.0
Vertex 7 edgeTo[7] = 0 distTo[7] = 8.0