### Sample Execution

#### Graph

Consider the following graph:

Note that this graph satisfies our input conditions:

- Directed,
- Non negative weights

We will now run Dijkstra(G, w, s) – where *‘s’* is our start vertex.

#### Initialization

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.

#### Round 1 of Loop Execution

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.

#### Round 2 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.

#### Round 3 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.

#### Round 4 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.

#### Round 5 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.

Note set Q is now empty, hence the loop terminates.

It is worth noticing the set S is the complement of set Q at the end of each loop execution.

Observe that, when a vertex is being added to the set S, it has the minimum “d” attribute, or we would have calculated the shortest-path weight already. Also means, any vertex added after that will have shortest-path weight greater than or equal to shortest-path weight of this edge. We will use this idea while we prove the correctness of the algorithm.

Pages: Contents … << Previous **6** Next Page>>

## One Comment Add yours