Suppose Dijkstras algorithm is run on the following graph, starting at node A.(a) Draw a

Problem 4.1

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.

Step by Step Solution

Step 1 of 8

Dijkstra’s Algorithm generates the shortest path tree (SPT) with a given source as root. Distance from source to each node will be the minimum distance.

The algorithm works as follows:

     1. Create the shortest path tree set – SPset which keeps track of the vertices added to SPT.

     2. Assign distance to source as 0 and all other vertices as infinite.

     3. While SPset does not contain all the vertices of graph,

          a. Take a vertex ‘p’ which is not in SPset with minimum distance value

          b. Add ‘p’ to SPset

          c. Update distance of neighbors of p. distance is updated as, for all neighbor q of p, if sum of distance value of p from source and weight of edge p-q, is less than distance value of q, then update distance value of q.