50.004-Homework Set 5 Solved

Question 1. Let G1 be a directed weighted graph with 5 vertices A,B,C,D,E. This graph G1 and its associated weight function w1 are depicted in Figure 1, where the values next to the edges represent the corresponding weights.

(i)      Run the Bellman–Ford algorithm on graph G1, with weight function w1 and source vertex A, using the relaxation order (A,B),(A,C),(B,C),(B,E),(B,D),(E,D),(D,C),(D,B). Please give the table of d and π values for all vertices, obtained at the end of each pass of all edges of G1 in the given relaxation order. The rows of your table should correspond to the iterations of the algorithm. You should include all iterations, including the initialization and the final check. You may write each entry of your table in the form of vertex(d,π).

(ii)    Next, consider a new weight function  on the same graph G1, where  3, and where  ) for all other edges e 6= (B,D) in G1. Run the Bellman–Ford algorithm on graph G1, with weight function   and source vertex A, using the same relaxation order as before. Please give the new table of d and π values for all vertices, obtained at the end of each pass of all edges of G1 in the given relaxation order. Again, you should include all iterations in your table, including the initialization and the final check.   

 

Figure 1: A directed weighted graph G1 for use in Question 1.

Question 2. Design an algorithm that satisfies the following conditions:

(i)      The algorithm takes as its inputs a directed weighted graph G, its associated weight function w, and a vertex s of G.

(ii)    The algorithm returns the adjacency matrix of a shortest-paths tree (for G) rooted at s, if G has no negative-weight cycles reachable from s, and returns the character string ‘error’ otherwise.

[Hint: Modify the Bellman–Ford algorithm.]       For the next two questions, consider a directed weighted graph G2 with 5 vertices s,t,x,y,z. This graph G2 and its associated weight function w2 are depicted in Figure 2, where the values next to the edges represent the corresponding weights.

 

Figure 2: A directed weighted graph G2 for use in Questions 3 and 4.

Question 3. Run Dijkstra’s algorithm on graph G2, with weight function w2 and source vertex x. In a table format, please give the d and π values of all vertices, as well as the set S and the priority queue Q, obtained at the end of each iteration of the while loop in Dijkstra’s algorithm. You may assume that Q is implemented using a min-heap, and you may write Q in its array representation. The first row of your table should correspond to the initialization. Each subsequent row of your table should correspond to an iteration of the while loop. Also, please draw the final shortest-paths tree for G2 as computed by Dijkstra’s algorithm.

Question 4. Run Dijkstra’s algorithm on graph G2, with weight function w2 and source vertex t. Similar to tbe previous question, please give in table format the d and π values of all vertices, as well as the set S and the priority queue Q, obtained at the end of each iteration of the while loop in Dijkstra’s algorithm. You may assume that Q is implemented using a min-heap, and you may write Q in its array representation. The first row of your table should correspond to the initialization. Each subsequent row of your table should correspond to an iteration of the while loop. Also, please draw the final shortest-paths tree for G2 as computed by Dijkstra’s algorithm.           

As discussed in class, when running Dijkstra’s algorithm on a directed weighted graph, we assume that the weights of all edges are all non-negative. In the next question, we shall take a closer look at an example to understand what happens when the weights of the edges are not all non-negative.

Question 5. Let G3 be a directed weighted graph with 4 vertices s,x,y,z, and with associated weight function w3. Suppose we run Dijkstra’s algorithm on G3 with weight function w3 and source vertex s. The initialized graph, together with the weights of all edges, and the d values of all vertices, are depicted in Figure 3. Values next to the edges represent the corresponding weights, while values indicated within circles represent the d values of the corresponding vertices. Please draw all subsequent graphs, together with the weights of all edges, and the d values of all vertices, that correspond to the end of each iteration of the while loop in Dijkstra’s algorithm. What is the corresponding “shortest-paths tree” for G3, as incorrectly computed by Dijkstra’s algorithm? What should be a correct shortest-paths tree for G3? In your own words, explain in detail why Dijkstra’s algorithm has failed to find a shortest path from s to z.

 

Figure 3: A directed weighted graph G3 for use in Question 5.