# Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Min Heap – Java Implementation

Earlier we have seen the basics of Dijkstra algorithm. In this article, we will see its implementation using the adjacency list and Min Heap.

brief: What is Dijkstra’s algorithm?

• Dijkstra algorithm is a greedy algorithm.
• It finds a shortest-path tree for a weighted undirected graph.
• This means it finds the shortest paths between nodes in a graph, which may represent, for example, road networks
• For a given source node in the graph, the algorithm finds the shortest path between the source node and every other node.
• This algorithm also used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.
• Dijkstra’s algorithm is very similar to Prim’s algorithm. In Prim’s algorithm, we create minimum spanning tree (MST) and in the Dijkstra algorithm, we create a shortest-path tree (SPT) from the given source.

We strongly recommend reading the following articles

Implementation – Adjacency List and Min Heap

• Create min Heap of size = no of vertices.
• Create a heapNode for each vertex which will store two pieces of information. a). vertex b). Distance from vertex from source vertex.
• Use spt[] to keep track of the vertices which are currently in min-heap.
• For each heapNode, initialize distance as +∞ except the heapNode for the source vertex for which distance will be 0.
• while minHeap is not empty
1. Extract the min node from the heap, say it vertex u, and add it to the SPT.
2. Decrease distance: For adjacent vertex v, if v is not in SPT[] and distance[v] > distance[u] + edge u-v weight then update distance[v] = distance[u] + edge u-v weight

Time Complexity:

Total vertices: V, Total Edges : E

• O(logV) – to extract each vertex from heap. So for V vertices – O(VlogV)
• O(logV) – each time decrease the distance of a vertex. Decrease distance will be called for at most once for each edge. So for total E edge – O(ElogV)
• So over all complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)

See the animation below for more understanding

Complete Code:

 import java.util.LinkedList; public class DijkstraUsingMinHeap { static class Edge { int source; int destination; int weight; public Edge(int source, int destination, int weight) { this.source = source; this.destination = destination; this.weight = weight; } } static class HeapNode{ int vertex; int distance; } static class Graph { int vertices; LinkedList[] adjacencylist; Graph(int vertices) { this.vertices = vertices; adjacencylist = new LinkedList[vertices]; //initialize adjacency lists for all the vertices for (int i = 0; i (); } } public void addEdge(int source, int destination, int weight) { Edge edge = new Edge(source, destination, weight); adjacencylist[source].addFirst(edge); edge = new Edge(destination, source, weight); adjacencylist[destination].addFirst(edge); //for undirected graph } public void dijkstra_GetMinDistances(int sourceVertex){ int INFINITY = Integer.MAX_VALUE; boolean[] SPT = new boolean[vertices]; // //create heapNode for all the vertices HeapNode [] heapNodes = new HeapNode[vertices]; for (int i = 0; i list = adjacencylist[extractedVertex]; for (int i = 0; i newKey){ decreaseKey(minHeap, newKey, destination); heapNodes[destination].distance = newKey; } } } } //print SPT printDijkstra(heapNodes, sourceVertex); } public void decreaseKey(MinHeap minHeap, int newKey, int vertex){ //get the index which distance's needs a decrease; int index = minHeap.indexes[vertex]; //get the node and update its value HeapNode node = minHeap.mH[index]; node.distance = newKey; minHeap.bubbleUp(index); } public void printDijkstra(HeapNode[] resultSet, int sourceVertex){ System.out.println("Dijkstra Algorithm: (Adjacency List + Min Heap)"); for (int i = 0; i 0 && mH[parentIdx].distance > mH[currentIdx].distance) { HeapNode currentNode = mH[currentIdx]; HeapNode parentNode = mH[parentIdx]; //swap the positions indexes[currentNode.vertex] = parentIdx; indexes[parentNode.vertex] = currentIdx; swap(currentIdx,parentIdx); currentIdx = parentIdx; parentIdx = parentIdx/2; } } public HeapNode extractMin() { HeapNode min = mH; HeapNode lastNode = mH[currentSize]; // update the indexes[] and move the last node to the top indexes[lastNode.vertex] = 1; mH = lastNode; mH[currentSize] = null; sinkDown(1); currentSize—; return min; } public void sinkDown(int k) { int smallest = k; int leftChildIdx = 2 * k; int rightChildIdx = 2 * k+1; if (leftChildIdx < heapSize() && mH[smallest].distance > mH[leftChildIdx].distance) { smallest = leftChildIdx; } if (rightChildIdx < heapSize() && mH[smallest].distance > mH[rightChildIdx].distance) { smallest = rightChildIdx; } if (smallest != k) { HeapNode smallestNode = mH[smallest]; HeapNode kNode = mH[k]; //swap the positions indexes[smallestNode.vertex] = k; indexes[kNode.vertex] = smallest; swap(k, smallest); sinkDown(smallest); } } public void swap(int a, int b) { HeapNode temp = mH[a]; mH[a] = mH[b]; mH[b] = temp; } public boolean isEmpty() { return currentSize == 0; } public int heapSize(){ return currentSize; } } public static void main(String[] args) { int vertices = 6; Graph graph = new Graph(vertices); int sourceVertex = 0; graph.addEdge(0, 1, 4); graph.addEdge(0, 2, 3); graph.addEdge(1, 2, 1); graph.addEdge(1, 3, 2); graph.addEdge(2, 3, 4); graph.addEdge(3, 4, 2); graph.addEdge(4, 5, 6); graph.dijkstra_GetMinDistances(sourceVertex); } }

Output:

```Dijkstra Algorithm: (Adjacency List + Min Heap)
Source Vertex: 0 to vertex 0 distance: 0
Source Vertex: 0 to vertex 1 distance: 4
Source Vertex: 0 to vertex 2 distance: 3
Source Vertex: 0 to vertex 3 distance: 6
Source Vertex: 0 to vertex 4 distance: 8
Source Vertex: 0 to vertex 5 distance: 14```