Perform the shortest s, t-path algorithm as described in the lectures. For each step, show the cut you are considering, the slacks of relevant edges, the width assignment for your cut, and all equality arcs.
computer science
Description
1. {10 marks} Perform the shortest s, t-path algorithm as described in the lectures. For each
step, show the cut you are considering, the slacks of relevant edges, the width assignment
for your cut, and all equality arcs. At the end of the algorithm, prove that your s, t-path is
the shortest using the width assignments you computed.
You may choose to use the worksheet provided on Learn for your solution.
2. {15 marks} Give a brief explanation for each of the following questions regarding the shortest
path algorithm.
Crowdmark note: Please put parts (a) and (b) in one submission box, and parts (c) and (d) in a separate submission box.
(a) Suppose the algorithm produces a shortest s, t-path sv1, v1v2, v2v3, . . . , vk−1vk, vkt. Explain why sv1, v1v2, . . . , vi−1vi is a shortest s, vi-path for any i = 1, . . . , k. (You do not need to use any graph theory.)
(b) For any edge e, explain why the slack of e is non-negative, and never increases throughout the shortest path algorithm.
(c) Consider the dual of the linear programming relaxation of the shortest s, t-path formulation for a graph G = (V, E).
