Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Bellman-Ford shortest paths: algorithm tracing] Consider the directed graph shown below. Run the Bellman-Ford shortest path algorithm we studied in class to find the shortest path from each node to the node d, and fill in the two-dimensional memorization array M[0..n, V] (provided below, where n = 5 is the number of nodes and V = {a, b, c, d, e} is the set of nodes in the graph). Each array entry should show the shortest path length and the immediate successor node (e.g., “8/e”). Your answers should include (i) the completed memorization table and (ii) a list of the shortest path and its path length for each node in the following format: “Shortest path from x to d: x – y – z – d (path length = 8)”, where x is a, b, c, or e. (Note path length is the sum of the weights of edges in the path.) You are encouraged to show the intermediate steps of computing the shortest path length for partial credit in case your answer is incorrect.
Memoization table:
a b c d e
0
1
2
3
4
(25) [Network flow Ford-Fulkerson algorithm tracing] Textbook Exercise 3 in Chapter 7. For the exercise a, state the s-t flow value and whether it is a maximum flow or not. For the exercise b, do the following steps to justify your answer for the exercise a:
Draw the residual graph of the flow network of Figure 7.27.
Show the trace of running the basic Ford-Fulkerson algorithm continuing from the residual graph drawn in the step i. In your trace, show both the flow network and the residual graph after each augmentation, if there is any.
Once the algorithm terminates, state the maximum flow value and the minimum cut (e.g., ({s, x, y, z}, {p, q, t}), and draw a line that shows the minimum cut in the final flow network.
Last modified: November 7, 2019
