In this problem, we will prove optimality of Dijkstra's algorithm through complementary slackness conditions of a carefully chosen linear program. (a) Consider computing a shortest s-t path in a directed graph G(V, E) with non-negative edge costs ce for each edge e E. Prove that every simple s-t path of G corresponds to a 0-1 feasible solution of the following linear program with the same object function value: subject to: min E cete e eE 2 e 1 for all S C V with s S, t & S e8+ (S) xe 0 for all e E. Note that 8+(S) denotes the edges sticking out of the set S. Formally, 8+(S) = {(u v) E: ue S, v S}. (b) What is the dual of this linear program? (c) What are the complementary slackness conditions? (d) Let P be the shortest s-t path returned by Dijkstra's algorithm. Prove that the solution to the linear program in (a) corresponding to P is an optimal solution, by exhibit- ing a dual feasible solution to the dual program in (b) such that complementary slackness conditions hold. [Hint: it is enough to use only dual variables of the form ys for subsets SCV correspond to the first i vertices processed by Dijkstra's algorithm. (for some i)]