After running INITIALIZE-SINGLE-SOURCE(G,s), will have v.d = ∞ except the start vertex ‘s’, which will have the key 0.

Note that we have put the keys in the circle of the vertex and weights along the edges, to simplify presentation of data.

The edge ‘s’ which has the least key value is shaded gray.

Q = {(s,0),(y,∞),(t,∞),(x,∞),(z,∞)}
S = Ø

Sets after initialization.

After initialization steps, Q = G.V and hence it is nonempty, so the loop runs.

Now, the vertex ‘s’ has the least key – hence we extract s and examine its neighbours, G.Adj[s] = {t, y}

Since t.d = ∞ > s.d + w(s,t), we relax the edge (s, t). That is, we set t.d = s.d + w(s, t) = 0 + 10 = 10 and we set ‘s’ as the parent of ‘t’.

Similarly, we will relax ‘y’, setting y.d = 5 and ‘s’ as its parent.

Note that we have shaded vertex ‘s’ black, since it is in the set S now, and ‘y’ is shaded gray since it is the vertex with least key. Also note that the edge (s, y) and (s, t) are shaded to notify that at the end of round 1 of loop execution, that’s the best shortest path to our knowledge – recorded in parent attribute, π of edges ‘y’ and ‘t’.

Q = {(y,5),(t,10),(x,∞),(z,∞)}
S = {s}

Sets after Round 1 of Loop Execution.

At the end of round 1, Q is nonempty, so the loop is executed.

Now, the vertex ‘y’ has the least key – hence we extract ‘y’ and examine its neighbours, G.Adj[y] = {t, x, z}

Since t.d = 10 > y.d + w(y,t), we relax that edge. That is, we change t.d = y.d + w(y,t) = 5 + 3 = 8 and we make ‘y’ as the new parent of ‘t’.

Similarly, we will relax edge (y,z), setting z.d = 7 and ‘y’ as its parent and edge (y,x), with x.d = 14 and x.π = y.

Note ‘y’ black since y ∈ S now, and ‘z’ is shaded gray since it is the vertex with least key.

Q = {(t,8),(x,14),(z,7)}
S = {s, y}

Sets after Round 2 of Loop Execution.

At the end of round 2, Q is nonempty, so the loop is executed.

Now, the vertex ‘z’ has the least key – hence we extract ‘z’ and examine its neighbours, G.Adj[z] = {s, x}

Since s.d = 0 < z.d + w(z, s), we skip the vertex ‘s’ this time, that is, we don’t relax the edge (z, s)

But we will relax (z, x), setting x.d = 13 and ‘z’ as its parent. You must be able to understand the change in shading by now.

Q = {(t,8),(x,13)}
S = {s, y, z}

Sets after Round 3 of Loop Execution.

At the end of round 3, Q = {t, x}, so the loop is executed.

Now, the vertex ‘t’ has the least key – hence we extract ‘t’ and examine its neighbours, G.Adj[t] = {y, x}

Since y.d = 5 < t.d + w(t, y), we skip the vertex ‘y’. But we will relax (t, x), setting x.d = 9 and ‘t’ as its parent.

Q = {(x,14)}
S = {s, y, z, t}

Sets after Round 4 of Loop Execution.

At the end of round 4, Q = {x}, so the loop is executed.

Now, the vertex ‘x’ has the least key (in fact the only vertex in set Q now!) – hence we extract ‘x’ and examine its neighbours, G.Adj[x] = {z}

Since z.d = 5 < x.d + w(x, z), we skip the vertex ‘z’.

Q = { }
S = {s, y, z, t, x}

Sets after Round 5 of Loop Execution.