Question

Suppose Dijkstra’s algorithm is run on the following graph, starting at node A.

a) Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm.

b) Show the final shortest-path tree.

Short answer

(a)The table showing the intermediate distance values is as follows.

(b)The final shortest-path tree is as follows:

Step-by-step solution

Explain Dijkstra’s algorithm

Dijkstra’s shortest-path algorithm marks all the distance of all the vertices as infinity. As the algorithm runs, when each vertex is visited, the distance between the vertices is calculated and the lowest distance values are updated at each iteration.

Show a table showing the intermediate distance values of all the nodes.

(a)

Consider the given graph ,

Set A as the starting node.

In the first iteration, set all the vertices values as $\infty$. At the second iteration, the path from A to B is set to 1. At the third iteration, path from A to C is updated to 3 since it is the shortest path.

At the fourth iteration, path from A to D is set to 4 , that is the total of (1+2+1) . At the fifth iteration A to E is set to 4 , that is the direct path.

At the sixth iteration, A to F is set to 8 , that is the direct path. At the seventh iteration, A to F is set to 7 , since it is comparatively lowest cost path.

At the nineth iteration, A to G is set to 7 at first, then it will be updated to 5 on the next iteration. At the last iteration, A to H is set to 8, and later it will be updated to 6 .

The table that shows the intermediate values is as follows,

Therefore, The table showing the intermediate distance values is obtained.

Step 3:Show the final shortest-path tree.

(b)

The final shortest-path tree have the shortest path with lowest distance cost is as follows,

Therefore, the above figure represents the final shortest-path tree.