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);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
        edgeTo = new int[V];
        distTo = new double[V];
        this.V = V;
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new Edge(from, to, 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;
        
        nodeRef[s] = pq.add(0.0, s);
        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;
            nodeRef[e.to] = pq.add(distTo[e.to], e.to);
            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.addEdge(0,1,5);   d.addEdge(3,6,9);   
        d.addEdge(0,4,9);   d.addEdge(4,5,4);
        d.addEdge(0,7,8);   d.addEdge(4,6,20);
        d.addEdge(1,2,12);  d.addEdge(4,7,5);
        d.addEdge(1,3,15);  d.addEdge(5,2,1);
        d.addEdge(1,7,4);   d.addEdge(5,6,13);
        d.addEdge(2,3,3);   d.addEdge(7,5,6);
        d.addEdge(2,6,11);  d.addEdge(7,2,7);
        
        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

No comments:

Post a Comment