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

Extract the min node from the heap, say it vertex u and add it to the SPT.

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:

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..-

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