Problem 3

1. Apply Dijkstra's algorithm on the graph shown alongside, starting from node A. Use a table like the one 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.

Draw the resulting shortest path tree.

2. For the same graph, run Prim's algorithm starting at node D and write the edges in the order they appear in the minimum spanning tree. Whenever you have a choice of nodes to pick from the queue, always pick the one that is alphabetically first. Draw the resulting tree and its cost.

3. Suppose after running Prim's algorithm, you realize that you made a mistake; Edge DE has a weight of 15 and not 1 as you thought. How can you compute the correct spanning tree 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, an edge (u, v) in the tree whose weight increases, and re-computes the spanning tree in linear time (without running Prim again). For full credit, you need to be precise about the steps your algorithm makes as well as its time.

4. 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.