8 4 6 5 6 b 5 2 e 6 a: It is easy to see that the shortest path from s to a iss > a, from s to b is s > > b, from s to c is s > C. Explain how Dijkstra's "dynamic programming algorithm would use this information to find the shortest path to e. What arcs are in the shortest path from s to e? What is the total length of the shortest path from s to e? b: What are the lengths of the shortest paths from s to d and from s to t? c: You have also seen a linear programming formulation for finding a shortest path. The idea is to send one unit of flow from the originating node to the terminating node as "cheaply" as possible, where the costs are given by the arc lengths. For the specific network considered in this problem, the linear program that determines the shortest path from s to t can be written like this: S .. 0 * 25 Fab + b Ibe + be s Minimize 43x4 +63 xb + 71 xe + Isab +27bc + Blad +61 +53be+bace + ls de +51 + 71 et Subject to - Tab I - = -1 Tad = 0 = 0 + bd Ida Id = 0 be+Ice+ 0 Id + = ... > 0 0 I I Id IE 1 1 Corresponding to the shortest s t path that you found in (b), there is a solution * to this linear program. Write out r*. d: Using variables named T3, Ta, Ttb, Te, Ad, Te, Tt corresponding to the equations in (c), write out the dual to the linear program in (c). e: Write out the complementary slackness condition associated with variable The f: Using the results you obtained in (a) and (b), let T be the length of a shortest tTM s > i path for each node i. (You can take the shortest s s path to be zero.) The vector 7* = (1, ..., ) is in fact an optimal solution for the dual linear program. Explain how you can tell that this is true, without applying any further algorithms. g: In light of the interpretation of the dual values in (f), what does the dual constraint - To+te