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

- Run the Bellman–Ford algorithm on graph
*G*_{1}, with weight function*w*_{1 }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*_{1 }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*_{1}, where 3, and where ) for all other edges*e*6= (*B,D*) in*G*_{1}. Run the Bellman–Ford algorithm on graph*G*_{1}, 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*_{1 }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*_{1 }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 Bellman–Ford algorithm.] [5 points] For the next two questions, consider a directed weighted graph *G*_{2 }with 5 vertices *s,**t,**x,**y,**z*. This graph *G*_{2 }and its associated weight function *w*_{2 }are depicted in Figure 2, where the values next to the edges represent the corresponding weights.

Figure 2: A directed weighted graph *G*_{2 }for use in Questions 3 and 4.

**Question 3. **Run Dijkstra’s algorithm on graph *G*_{2}, with weight function *w*_{2 }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 *G*_{2 }as computed by Dijkstra’s algorithm. [5 points]

**Question 4. **Run Dijkstra’s algorithm on graph *G*_{2}, with weight function *w*_{2 }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 *G*_{2 }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 *G*_{3 }be a directed weighted graph with 4 vertices *s,x,y,z*, and with associated weight function *w*_{3}. Suppose we run Dijkstra’s algorithm on *G*_{3 }with weight function *w*_{3 }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 *G*_{3}, as incorrectly computed by Dijkstra’s algorithm? What should be a correct shortest-paths tree for *G*_{3}? In your own words, explain in detail why Dijkstra’s algorithm has failed to find a shortest path from *s *to *z*. [5 points]

Figure 3: A directed weighted graph *G*_{3 }for use in Question 5.

## Reviews

There are no reviews yet.