Reference no: EM13335147

Submit your solution electronically at https://moodle.cs.colorado.edu,orturninthepaperversionbeforeclass.Makesure to include your name, student id, email address, and the Honor Code Pledge.

1. Answer the following questions for the graph G given above. You can either compute the results manually, or write a program using a language of your choice and print out the results.

(a) If using the Bellman-Ford algorithm to find the shortest paths from S to other vertices:

(i) draw a table showing the intermediate distance values of all vertices at each iteration of the algorithm;

(ii) show the final shortest-path tree.

(b) Add 5 to each edge weight such that all edges in the graph have positive weights.Suppose Dijkstras algorithm is run on the new graph G0 with starting node S:

(i) draw a table showing the intermediate distance values of all vertices at each iteration of the algorithm; (ii) show the final shortest-path tree.

(c) Are the shortest paths found in (a) and (b) the same for each vertex

2. You are given a strongly connected directed graph G =(V,E) with positive edge weights along with a particular node v0 2 V  .Give an effcient algorithm for finding shortest paths between all pairs of nodes, with the one restriction that these paths must all pass through v0. Describe your algorithm in word so write down the pseudo code. And analyze its time complexity.