In this problem, we will prove optimality of Dijkstra's algorithm through complementary slackness conditions of a...

Transcribed Image Text:

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 eЄE 2 Σe ≥1 for all S C V with s € S, t & S e€8+ (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)] 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 eЄE 2 Σe ≥1 for all S C V with s € S, t & S e€8+ (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)]

Answer rating: 100% (QA)

Step 1 a To prove that every simple st path of G corresponds to a 01 feasible solution of the given linear program we need to show that for every simp... View the full answer