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 adjacency list and Min Heap.

We strongly recommend reading the following articles

  1. Dijkstra algorithm and how it works
  2. Adjacency List
  3. Implementation of min-Heap

Example:
Dijkstra - Shortest Path Algorithm

Implementation – Adjacency List and Min Heap

  • Create min Heap of size = no of vertices.
  • Create a heapNode for each vertex which will store two 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

1-32
previous arrow
next arrow
PlayPause
Slider

Complete Code:


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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: