Task 1 (Applying Dijkstra's Shortest Path Algorithm) 25 points 5 2 24 22 1 2 Figure 1: A directed graph Fig. 1 shows a directed graph that represents a transportation network. The given arc weights are the travel distances for traversing the arc. Determine a shortest path that starts in node 1 and terminates in node 6. Use the tabular representation (Tab. 1) to store and present the label values developed during the iterations. Indicate the identified shortest path and give the associated travel distance. Mark every permant label value by an *. Indicate the associated predecessor node for each label. Task 3 (Max Flow Determination) 18 points Assume now, that the numbers shown in Fig. 1 represent the upper bounds of the arc capacities and 0 is the lower bound. We are looking for a maximal flow through the resulting network (without the additional arc (6; 1)!) starting in 1 and terminating in 6. Assume that the following network flow is given: 212 = 1, 22:8 = 1, 19;3 = 1, 13,6 = 1, 21:4 = 2, 245 = 2 and 256 = 2. a) What is the objective function value of the current flow? b) Apply the flow improvement procedure discussed in lecture to identify the maximal flow. Explain the identified flow using the optimal Xij-values. c) What is the objective function value of the identified flow