A weighted directed graph is shown in Figure 1. Answer the following questions. (a) Consider breadth-first...

  

Transcribed Image Text:

A weighted directed graph is shown in Figure 1. Answer the following questions. (a) Consider breadth-first traversal from the node A over the directed graph (Figure 1), where the weights on the graph are ignored. Show the node and the content of the queue, when the a breadth-first traversal visits a node for every node in iteration. Give the final breadth-first traversal result. [10 marks] (b) Consider computing the single source shortest paths over the weighted directed graph (Fig- ure 1) based on the Dijkstra's algorithm. Recall that S is the set of nodes whose shortest distance is known, d(v) is the current distance from the source node to v, and p(v) is the predecessor node along the path from the source to v. Let the node A be the source node. (i) Show the initial S, and initial d(v) and p(v) for every node in the graph excluding the source node. [2 marks] (ii) Show how Dijkstra's algorithm works step by step from the single source node to all other nodes by showing how d(v) and p(v) are changed for every node v in the graph, while S is becoming larger in every iteration. [20 marks] (iii) Show the shortest paths from the source node to all other nodes based on your answer of (ii). [4 marks] (iv) Explain the condition for the Dijkstra's algorithm to work, and show how the Dijkstra's algorithm does not work if the condition is violated using an example. [4 marks] A 3 5. B 3 F 22 12 E H 2 7 V 2 2 19 2 31. D Figure 1: A weighted directed graph A weighted directed graph is shown in Figure 1. Answer the following questions. (a) Consider breadth-first traversal from the node A over the directed graph (Figure 1), where the weights on the graph are ignored. Show the node and the content of the queue, when the a breadth-first traversal visits a node for every node in iteration. Give the final breadth-first traversal result. [10 marks] (b) Consider computing the single source shortest paths over the weighted directed graph (Fig- ure 1) based on the Dijkstra's algorithm. Recall that S is the set of nodes whose shortest distance is known, d(v) is the current distance from the source node to v, and p(v) is the predecessor node along the path from the source to v. Let the node A be the source node. (i) Show the initial S, and initial d(v) and p(v) for every node in the graph excluding the source node. [2 marks] (ii) Show how Dijkstra's algorithm works step by step from the single source node to all other nodes by showing how d(v) and p(v) are changed for every node v in the graph, while S is becoming larger in every iteration. [20 marks] (iii) Show the shortest paths from the source node to all other nodes based on your answer of (ii). [4 marks] (iv) Explain the condition for the Dijkstra's algorithm to work, and show how the Dijkstra's algorithm does not work if the condition is violated using an example. [4 marks] A 3 5. B 3 F 22 12 E H 2 7 V 2 2 19 2 31. D Figure 1: A weighted directed graph