Operation of Algorithm

The following sequence of diagrams shows the operation of Dijkstra's Algorithm. The bold vertices show the vertex to which shortest path has been find out.

Step 1:

Initialize the graph, all of the vertices have infinite costs except the source vertex that has zero cost

 Step 2

From all the adjacent vertices, select the closest vertex to the source s.

As we initialized d[s] through 0, it's s. (illustrated in bold circle)

Add it to S

Relax all vertices adjacent to s, that means u & x

Update vertices u & x by 10 & 5 as the distance from s.

            Step 3:

Select the nearest vertex, x. Relax all of vertices adjacent to x

Update predecessors for u, v & y. Predecessor of x = s

Predecessor of v = x ,s

Predecessor of y = x ,s

add x to S

Step 4:

Now y is the closest vertex. Add it to S.

Relax v and adjust its predecessor.

 Step 5:           

u is now closest, add it to S and adjust its adjacent vertex, v.

Step 6:

Finally, add v to S.

The predecessor list now defines the shortest path from each node to s.