The following picture shows an example of a Korchoff Graph. It is a weighted, directed graph....

 

Transcribed Image Text:

The following picture shows an example of a Korchoff Graph. It is a weighted, directed graph. As you can see the graph has a binary tree component at is center. Moreover, there are edges going from each leaf of the binary tree backto the root. All edges are weighted and the weights are non-negative. We wish to compute single-source shortest paths in a Korchoff graph. 16 4 23 17 5 b->i: 0 (b,i) b> d: 40 (b,c,d) b>e: 24, (b, i, a, e) b> f: 25, (b, i, a, e, f) b->g: 34, (b, i, a, e, f, g) b> h: 39, (b, i, a, e, f, h) 0 8 1 14 42 7 For example, the shortest path costs from vertex 'b' to all other vertices are as follows: ba: 16, (b, i, a) b->c: 17 (b,c) a) Is the following statement true or false? Justify your answer: Dijkstra's shortest path algorithm takes O(IV|lg|V) time on a Korchoff graph. b) Design a Single Source shortest path algorithm for the Korchoff graph which works in linear time. The call to the algorithm looks like: spKorchoff(G=(V, E), s, r), where G is a Korchoff graph, s is the source node used to measure the shortest paths, and r is the root node of the binary tree component of the graph. First describe the algorithm in few lines (or steps) in English, then write the pseudocode. The following picture shows an example of a Korchoff Graph. It is a weighted, directed graph. As you can see the graph has a binary tree component at is center. Moreover, there are edges going from each leaf of the binary tree backto the root. All edges are weighted and the weights are non-negative. We wish to compute single-source shortest paths in a Korchoff graph. 16 4 23 17 5 b->i: 0 (b,i) b> d: 40 (b,c,d) b>e: 24, (b, i, a, e) b> f: 25, (b, i, a, e, f) b->g: 34, (b, i, a, e, f, g) b> h: 39, (b, i, a, e, f, h) 0 8 1 14 42 7 For example, the shortest path costs from vertex 'b' to all other vertices are as follows: ba: 16, (b, i, a) b->c: 17 (b,c) a) Is the following statement true or false? Justify your answer: Dijkstra's shortest path algorithm takes O(IV|lg|V) time on a Korchoff graph. b) Design a Single Source shortest path algorithm for the Korchoff graph which works in linear time. The call to the algorithm looks like: spKorchoff(G=(V, E), s, r), where G is a Korchoff graph, s is the source node used to measure the shortest paths, and r is the root node of the binary tree component of the graph. First describe the algorithm in few lines (or steps) in English, then write the pseudocode.

Answer rating: 100% (QA)

Ansia Adjacancy Matrix S a 9 AA fo A B Al IJAWILL B D F A O 1 2 Ans 6 Adjacancy Gistaph 13 17 1 A1 ... View the full answer