ANOTHER answers ANSWER UNLESS IT'S IDENTICAL OR -1**
- Please Solve It On Your Own And Don T Copy From Another Chegg Answer Unless It S Identical Or 1 Please Solve Part 2 1 (127.78 KiB) Viewed 19 times
7 11 7 Problem 4 (20 points) 1. (5 points) Apply Dijkstra's algorithm on the graph shown alongside, starting from node A. Use a table like the one shown below to compute the distances of all nodes and their order in which they are processed at each step. Whenever you have a choice of nodes to pick from the queue, always pick the one that is alphabetically first. Show the resulting shortest path tree. E (A 10 H 3 Step # Order A dist[A] 0 dist dist C dist [D dist 0 00 00 00 1 2 2. (5 points) For the same graph, run Prim's algorithm starting at node C and write the edges in the order they appear in the minimum spanning tree. Draw the resulting tree and its cost. 3. (5 points) Suppose after running Prim's algorithm, you realize that the correct weight of edge CD is 2 and not 7. How can you compute the correct spanning tree from the existing one without having to run Prim's algorithm again? Your goal is to give a general algorithm for the problem which is given as input an existing tree T and an edge e with weight smaller than the original and computes the updated tree in linear time. Hint: Look at the cut property again. 4. (5 points) Run Kruskal's algorithm and write the edges in the order they appear in the minimum spanning tree. Draw the resulting tree and its cost.