Implementation in java for Dijkstra's algorithm to find the shortest path

Hello Friends,

Today I am here with you with Dijkstra's algorithm to find the shortest path.
Dijkstra Algorithm uses MinPriorityQueue which usually is implemented using MinHeap.  MinPriorityQueue is a queue which always removes the item with lowest value and not in usual FIFO way.  But as Heap implementation is little complex so first lets use simple Queue and modify its remove() method to implement the MinPriorityQueue. Later in the post I have implemented the algorithm with MinHeap also, which is better in performance.




For the first implementation using simple Queue, I am using above graph to to compute the minimum distances from Node 1 to all other nodes.  Note that Nodes 9,10 and 11 are not reachable from our source node.

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic implementation of Dijkstra Algorithm using Simple Queue with Graph using Adjacency list.
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph
    private MinPriorityQueue queue;

    public Graph(int size) {
        this.size = size;
        vertices = new Node[size];
        addNodes();
        queue = new MinPriorityQueue(size);
    }

    public class Node {
        int name;
        int cost;
        Neighbour neighbourList;
        State state;

        Node(int name) {
            this.name = name;
            state = State.NEW;
            cost = Integer.MAX_VALUE;
        }
    }

    public class Neighbour {
        int index;
        int weight;
        Neighbour next;

        public Neighbour(int index, Neighbour next, int weight) {
            this.index = index;
            this.next = next;
            this.weight = weight;
        }
    }

    private void addNodes() {
        for (int i = 1; i <= size; i++) {
            addNode(i);
        }
    }

    public void addNode(int name) {
        vertices[name - 1] = new Node(name);
    }

    public void addEdge(int sourceName, int destiName, int weight) {
        int srcIndex = sourceName - 1;
        int destiIndex = destiName - 1;
        Node srcNode = vertices[srcIndex];
        Node destiNode = vertices[destiIndex];
        srcNode.neighbourList = new Neighbour(destiIndex, srcNode.neighbourList, weight);
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        destiNode.neighbourList = new Neighbour(srcIndex, destiNode.neighbourList, weight);
    }

    public void computeSortestPathsFrom(int sourceNodeName) {
        for (int i = 0; i < size; i++) {
            if (vertices[i].name == sourceNodeName) {
                applyDijkstraAlgorithm(vertices[i]);
                break;// in this case we need not traverse the nodes which are
                        // not reachable from the source Node
            }
        }
    }

    /**
     * The algorithm is based upon BFS.
     */
    private void applyDijkstraAlgorithm(Node sourceNode) {
        queue.add(sourceNode);
        sourceNode.state = State.IN_Q;
        sourceNode.cost = 0; // cost of reaching Source from Source Node itself
                                // is 0, for all others we still need to
                                // discover the cost so the cost for them has
                                // been already initialized to Integer.MAX_VALUE
        while (!queue.isEmpty()) {
            Node visitedNode = queue.remove();
            visitedNode.state = State.VISITED;
            Neighbour connectedEdge = visitedNode.neighbourList;
            while (connectedEdge != null) {
                Node neighbour = vertices[connectedEdge.index];
                // adding the not enqued neighbor nodes in the queue
                if (neighbour.state == State.NEW) {
                    queue.add(neighbour);
                    neighbour.state = State.IN_Q;
                }
                // updating [relaxing] the costs of each non visited neighbor
                // node if its
                // have been made lesser.
                if (neighbour.state != State.VISITED && ((connectedEdge.weight + visitedNode.cost) < neighbour.cost)) {
                    neighbour.cost = connectedEdge.weight + visitedNode.cost;
                }
                connectedEdge = connectedEdge.next;
            }
        }
        
        //now printing the shortest distances
        for(int i = 0; i < size; i++){
            if(vertices[i].cost != Integer.MAX_VALUE){
                System.out.println("distance from "+sourceNode.name +" to "+vertices[i].name+" is " +vertices[i].cost);
            }else{
                System.out.println(vertices[i].name +" is not reachable from "+sourceNode.name);
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Ideally MinPriority Queue
     * should be implemented using Heap but for making it easy to understand
     * currently implementation of Normal Queue (its remove() method()) has been
     * modified.
     *
     */
    public class MinPriorityQueue {
        Node[] queue;
        int maxSize;
        int rear = -1, front = -1;

        MinPriorityQueue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Node[maxSize];
        }

        public void add(Node node) {
            queue[++rear] = node;
        }

        public Node remove() {
            Node minValuedNode = null;
            int minValue = Integer.MAX_VALUE;
            int minValueIndex = -1;
            front++;
            for (int i = front; i <= rear; i++) {
                if (queue[i].state == State.IN_Q && queue[i].cost < minValue) {
                    minValue = queue[i].cost;
                    minValuedNode = queue[i];
                    minValueIndex = i;
                }
            }

            swap(front, minValueIndex); // this ensures deletion is still done
                                        // from front;
            queue[front] = null;// lets not hold up unnecessary references in
                                // the queue
            return minValuedNode;
        }

        public void swap(int index1, int index2) {
            Node temp = queue[index1];
            queue[index1] = queue[index2];
            queue[index2] = temp;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(11);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 2, 3);
        graph.addEdge(2, 5, 5);
        graph.addEdge(2, 4, 3);
        graph.addEdge(3, 5, 8);
        graph.addEdge(3, 6, 5);
        graph.addEdge(4, 5, 1);
        graph.addEdge(4, 7, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(5, 8, 8);
        graph.addEdge(5, 7, 2);
        graph.addEdge(6, 8, 15);
        graph.addEdge(7, 8, 5);
        graph.addEdge(9, 11, 2);
        graph.computeSortestPathsFrom(1);
    }
}

Output :
distance from 1 to 1 is 0
distance from 1 to 2 is 3
distance from 1 to 3 is 1
distance from 1 to 4 is 6
distance from 1 to 5 is 7
distance from 1 to 6 is 6
distance from 1 to 7 is 9
distance from 1 to 8 is 14
9 is not reachable from 1
10 is not reachable from 1
11 is not reachable from 1

Now having a look at the Dijkstra's Algorithm using simple Queue to implement the MinPriorityQueue, lets see below the better performance version of the algorithm where we will use MinHeap for the implementation of MinPriorityQueue. Note that we should implement our own MinHeap because PriorityQueue from java.util package does not take care of updating the priority of the items already added in the queue, in case there is some changes in the internal parameters of the items which are already added in the priority queue.

public class DikjstraAlgorithm {
    public static void main(String[] args) {

        Graph graph = new Graph(9);
        for (int i = 0; i < 9; i++) {
            graph.addVertex(i);
        }
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 7, 8);
        graph.addEdge(1, 0, 4);
        graph.addEdge(1, 7, 11);
        graph.addEdge(1, 2, 8);
        graph.addEdge(2, 1, 8);
        graph.addEdge(2, 3, 7);
        graph.addEdge(2, 8, 2);
        graph.addEdge(2, 5, 4);
        graph.addEdge(3, 2, 7);
        graph.addEdge(3, 4, 9);
        graph.addEdge(3, 5, 14);
        graph.addEdge(4, 3, 9);
        graph.addEdge(4, 5, 10);
        graph.addEdge(5, 2, 4);
        graph.addEdge(5, 3, 14);
        graph.addEdge(5, 4, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(6, 5, 2);
        graph.addEdge(6, 7, 1);
        graph.addEdge(6, 8, 6);
        graph.addEdge(7, 0, 8);
        graph.addEdge(7, 1, 11);
        graph.addEdge(7, 6, 1);
        graph.addEdge(7, 8, 7);
        graph.addEdge(8, 2, 2);
        graph.addEdge(8, 6, 6);
        graph.addEdge(8, 7, 7);
        graph.findShortestPaths(0);
    }

    public static class Graph {
        Vertex[] vertices;
        int maxSize;
        int size;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
        }

        public void addVertex(int name) {
            vertices[size++] = new Vertex(name);
        }

        public void addEdge(int sourceName, int destinationName, int weight) {
            int srcIndex = sourceName;
            int destiIndex = destinationName;
            vertices[srcIndex].adj = new Neighbour(destiIndex, weight, vertices[srcIndex].adj);
            vertices[destiIndex].indegree++;
        }
        
        public void findShortestPaths(int sourceName){
            applyDikjstraAlgorith(vertices[sourceName]);
            for(int i = 0; i < maxSize; i++){
                System.out.println("Distance of "+vertices[i].name+" from Source: "+ vertices[i].cost);
            }
        }
        
        public class Vertex {
            int cost;
            int name;
            Neighbour adj;
            int indegree;
            State state;

            public Vertex(int name) {
                this.name = name;
                cost = Integer.MAX_VALUE;
                state = State.NEW;
            }

            public int compareTo(Vertex v) {
                if (this.cost == v.cost) {
                    return 0;
                }
                if (this.cost < v.cost) {
                    return -1;
                }
                return 1;
            }
        }

        public enum State {
            NEW, IN_Q, VISITED
        }

        public class Neighbour {
            int index;
            Neighbour next;
            int weight;

            Neighbour(int index, int weight, Neighbour next) {
                this.index = index;
                this.next = next;
                this.weight = weight;
            }
        }

        public void applyDikjstraAlgorith(Vertex src) {
            Heap heap = new Heap(maxSize);
            heap.add(src);
            src.state = State.IN_Q;
            src.cost = 0;
            while (!heap.isEmpty()) {
                Vertex u = heap.remove();
                u.state = State.VISITED;
                Neighbour temp = u.adj;
                while (temp != null) {
                    if (vertices[temp.index].state == State.NEW) {
                        heap.add(vertices[temp.index]);
                        vertices[temp.index].state = State.IN_Q;
                    }
                    if (vertices[temp.index].cost > u.cost + temp.weight) {
                        vertices[temp.index].cost = u.cost + temp.weight;
                        heap.heapifyUP(vertices[temp.index]);
                    }
                    temp = temp.next;
                }
            }
        }

        public static class Heap {
            private Vertex[] heap;
            private int maxSize;
            private int size;

            public Heap(int maxSize) {
                this.maxSize = maxSize;
                heap = new Vertex[maxSize];
            }

            public void add(Vertex u) {
                heap[size++] = u;
                heapifyUP(size - 1);
            }

            public void heapifyUP(Vertex u) {
                for (int i = 0; i < maxSize; i++) {
                    if (u == heap[i]) {
                        heapifyUP(i);
                        break;
                    }
                }
            }

            public void heapifyUP(int position) {
                int currentIndex = position;
                Vertex currentItem = heap[currentIndex];
                int parentIndex = (currentIndex - 1) / 2;
                Vertex parentItem = heap[parentIndex];
                while (currentItem.compareTo(parentItem) == -1) {
                    swap(currentIndex, parentIndex);
                    currentIndex = parentIndex;
                    if (currentIndex == 0) {
                        break;
                    }
                    currentItem = heap[currentIndex];
                    parentIndex = (currentIndex - 1) / 2;
                    parentItem = heap[parentIndex];
                }
            }

            public Vertex remove() {
                Vertex v = heap[0];
                swap(0, size - 1);
                heap[size - 1] = null;
                size--;
                heapifyDown(0);
                return v;
            }

            public void heapifyDown(int postion) {
                if (size == 1) {
                    return;
                }

                int currentIndex = postion;
                Vertex currentItem = heap[currentIndex];
                int leftChildIndex = 2 * currentIndex + 1;
                int rightChildIndex = 2 * currentIndex + 2;
                int childIndex;
                if (heap[leftChildIndex] == null) {
                    return;
                }
                if (heap[rightChildIndex] == null) {
                    childIndex = leftChildIndex;
                } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) {
                    childIndex = rightChildIndex;
                } else {
                    childIndex = leftChildIndex;
                }
                Vertex childItem = heap[childIndex];
                while (currentItem.compareTo(childItem) == 1) {
                    swap(currentIndex, childIndex);
                    currentIndex = childIndex;
                    currentItem = heap[currentIndex];
                    leftChildIndex = 2 * currentIndex + 1;
                    rightChildIndex = 2 * currentIndex + 2;
                    if (heap[leftChildIndex] == null) {
                        return;
                    }
                    if (heap[rightChildIndex] == null) {
                        childIndex = leftChildIndex;
                    } else if (heap[rightChildIndex].compareTo(heap[leftChildIndex]) == -1) {
                        childIndex = rightChildIndex;
                    } else {
                        childIndex = leftChildIndex;
                    }
                }
            }

            public void swap(int index1, int index2) {
                Vertex temp = heap[index1];
                heap[index1] = heap[index2];
                heap[index2] = temp;
            }

            public boolean isEmpty() {

                return size == 0;
            }
        }
    }
}

Output :
Distance of 0 from Source: 0
Distance of 1 from Source: 4
Distance of 2 from Source: 12
Distance of 3 from Source: 19
Distance of 4 from Source: 21
Distance of 5 from Source: 11
Distance of 6 from Source: 9
Distance of 7 from Source: 8
Distance of 8 from Source: 14