Dijkstra's algorithm

Dijkstra algorithm

Step-01:

 

The following two sets are created-

Unvisited set : {S , a , b , c , d , e}

Visited set     : { }

Step-02:

-------------------------------------------------------------------------

Vertex ‘S’ is chosen.

d[S] + 1 = 0 + 1 = 1 < ∞

∴ d[a] = 1 and Π[a] = S

d[S] + 5 = 0 + 5 = 5 < ∞

∴ d[b] = 5 and Π[b] = S

Before Edge Relaxation-

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

Unvisited set : {a , b , c , d , e}

Visited set : {S}

----------------------------------------------------------------------------------

Vertex ‘a’ is chosen.

This is because shortest path estimate for vertex ‘a’ is least.

The outgoing edges of vertex ‘a’ are relaxed.

Now,

d[a] + 2 = 1 + 2 = 3 < ∞

∴ d[c] = 3 and Π[c] = a

d[a] + 1 = 1 + 1 = 2 < ∞

∴ d[d] = 2 and Π[d] = a

d[b] + 2 = 1 + 2 = 3 < 5

∴ d[b] = 3 and Π[b] = a

After edge relaxation, our shortest path tree is-

Before Edge Relaxation-

Now, the sets are updated as-

Unvisited set : {b , c , d , e}

Visited set : {S , a}

----------------------------------------------------------------------------

Step-05:

 

Vertex ‘d’ is chosen.

This is because shortest path estimate for vertex ‘d’ is least.

The outgoing edges of vertex ‘d’ are relaxed.

Before Edge Relaxation-

Now,

d[d] + 2 = 2 + 2 = 4 < ∞

∴ d[e] = 4 and Π[e] = d

 

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

Unvisited set : {b , c , e}

Visited set : {S , a , d}

------------------------------------------------------------------------

Step-06:

 

Vertex ‘b’ is chosen.

This is because shortest path estimate for vertex ‘b’ is least.

Vertex ‘c’ may also be chosen since for both the vertices, shortest path estimate is least.

The outgoing edges of vertex ‘b’ are relaxed.

Before Edge Relaxation-

Now,

d[b] + 2 = 3 + 2 = 5 > 2

∴ No change

 

After edge relaxation, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

Unvisited set : {c , e}

Visited set     : {S , a , d , b}

--------------------------------------------------------------------------

Step-07:

 

Vertex ‘c’ is chosen.

This is because shortest path estimate for vertex ‘c’ is least.

The outgoing edges of vertex ‘c’ are relaxed.

Before Edge Relaxation-

Now,

d[c] + 1 = 3 + 1 = 4 = 4

∴ No change

 

After edge relaxation, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

Unvisited set : {e}

Visited set : {S , a , d , b , c}

 

----------------------------------------------------------------------------

Step-08:

 

Vertex ‘e’ is chosen.

This is because shortest path estimate for vertex ‘e’ is least.

The outgoing edges of vertex ‘e’ are relaxed.

There are no outgoing edges for vertex ‘e’.

So, our shortest path tree remains the same as in Step-05.

 

Now, the sets are updated as-

Unvisited set : {S , a , d , b , c , e }

Visited set : {}

 

Now,

All vertices of the graph are processed.

Our final shortest path tree is as shown below.

It represents the shortest path from source vertex ‘S’ to all other remaining vertices.

----------------------------------------------------------------------------

The order in which all the vertices are processed is :

S , a , d , b , c , e.

-----------------------------------------------------------------------------