Dijkstra's algorithm solves the single source shortest path problem when all edges have non negative weights. algorithm starts at the source vertex S, it grows a tree that ultimately spans all vertices reachable from S. Vertices are added to tree in order of distance i.e., first S, the vertices closest to S, then the next closest and so on.

Dijkstra(G, W, S)
S<-{}
Initialize priority queue Q i.e.,Q<-V[G]
while priority queue Q is not empty do
    u<-Extract_Min(Q)
S<-S ⋃ {u}
for each vertex v ∈ Adj[u] do
    Relax(u, v, w)    				

Relax(u, v, w)
if d[u] + w(u, v) < d[v] then
    d[v]<-d[u] + w(u, v)
    π[v]<-u				

Let's take an example which is shown below.

Step 1:All nodes have set infinite distance except the source node S which is set as 0.

Step 2:Relax all nodes adjacent to source S.Adj[s]={u, x}.

Apply relax(s, u, w) and relax(s, x, w)

Step 3:Choose the closest node x.Relax all nodes adjacent to x.Adj[x]={u, y, v}

Apply relax(x, u, w) ,relax(x, u, w) and relax(x, v, w)

Step 4:Now, node y is the closest node.Adj[y]={v}

Apply relax(y, v, w)

Step 5:Now, the closest node is u.Adj[u]={v, x}

Relax (u, x, w) and relax(u, v, w)

Step 6:Finally, we get the shortest distance of each vertex from the source s.

Source Code of Dijkstra's Algorithm

Happy Exploring!