[Solved] 50.004 Homework Set5

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

• Run the BellmanFord algorithm on graph G₁, with weight function w₁ 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 G₁ 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,). [2 points]
• Next, consider a new weight function on the same graph G₁, where 3, and where ) for all other edges e 6= (B,D) in G₁. Run the BellmanFord algorithm on graph G₁, 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 G₁ 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 G₁ for use in Question 1.

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

• The algorithm takes as its inputs a directed weighted graph G, its associated weight function w, and a vertex s of G.
• 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 BellmanFord algorithm.] [5 points] For the next two questions, consider a directed weighted graph G₂ with 5 vertices s,t,x,y,z. This graph G₂ and its associated weight function w₂ are depicted in Figure 2, where the values next to the edges represent the corresponding weights.

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

Question 3. Run Dijkstras algorithm on graph G₂, with weight function w₂ 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 Dijkstras 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 G₂ as computed by Dijkstras algorithm. [5 points]

Question 4. Run Dijkstras algorithm on graph G₂, with weight function w₂ 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 Dijkstras 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 G₂ as computed by Dijkstras algorithm.

As discussed in class, when running Dijkstras 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 G₃ be a directed weighted graph with 4 vertices s,x,y,z, and with associated weight function w₃. Suppose we run Dijkstras algorithm on G₃ with weight function w₃ 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 Dijkstras algorithm. What is the corresponding shortest-paths tree for G₃, as incorrectly computed by Dijkstras algorithm? What should be a correct shortest-paths tree for G₃? In your own words, explain in detail why Dijkstras algorithm has failed to find a shortest path from s to z. [5 points]

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