Question

Question 1 (1.5 marks) Consider the subnet of the following figure. Shortest Path routing is used, and the weights on each edge is shown. Compute the shortest path from E to D using Dijkstra's algorithm. Show your steps and describe your figures briefly. 4

Answer 1

Dijkstra's Algorithm : It is Single Source Shortest Path Algorithm, that is it is used to find the shortest path form a single source node to all the other nodes in the graph.

For this we maintain a set of visited and unvisited vertex set, which means the set of vertex whose shortest path are discovered by the algorithm and the set of vertex whose shortest path is yet to be discovered.

Initially our vertex set table looks like :

Vertex() Distance(d) Through

Since we need to compute shortest path from E to D, therefore our Source Node is E

therefore Traversing E, and updating table that is writing the distance of every other node from E

On first iteration, we visited E, Table after first iteration :

Now the shortest path from node E is to node F, therefore traversing F

On second iteration, we visited F, Table after second iteration :

Vertex() Distance(d) Through 4

Now the shortest path from node E is to node C, therefore traversing C

On third iteration, we visited C, Table after third iteration :

Vertex() Distance(d) Through

Now the shortest path from node E is to node B, therefore traversing B

On fourth iteration, we visited B, Table after fourth iteration :

since there is no shortest to any node through B, therefore table is unchanged

Now the shortest path from node E is to node D, therefore traversing D

On fifth iteration, we visited D, Table after fifth iteration :

since there is no shortest to any node through D, therefore table is unchanged

Now the shortest path from node E is to node A, therefore traversing A

On sixth iteration, we visited A, Table after sixth iteration :

since there is no shortest to any node through A, therefore table is unchanged

Thus, we have traversed all the nodes from the Source Node i.e., Node E

and the shortest path from Node E to Node D is 6 through C.