A Bit About Dijkstra’s

Sample Execution

Graph

Consider the following graph:

Note that this graph satisfies our input conditions:

  1. Directed,
  2. Non negative weights

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

Graph G

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.

Graph G, respective keys of edges after initialization.
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’.

Graph after Round 1 of Loop execution.
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.

Graph after Round 2 of Loop Execution
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.

Graph after Round 3 of Loop Execution.
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.

Graph after Round 4 of Loop Execution.
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’.

Graph after Round 5 of Loop Execution
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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.