Formulate the following single source shortest path problem as a circulation problem.

please refer to the picture attached as it contains the whole question, thanks

Hw 1 2017(1).d0 !Compatibility Mode-word File Insert Design Layout References Mailings Review View Zotera Tell me what you want to d... Home Cut Copy Format Painter Sign in Share Calibri (Body)2- Replace Paste B 1 u . abEx, x' A.,A, A. | TNormal TNO Spac Heading 1 Heading 2 Title Subtitle Subtle Em Emphasis Intense E ,-. Select Clipboard Font Styles Editing Problem 4 (20 points) Formulate the following single source shortest path problem as a circulation problem. b(1) 0 cost, min. cap., max. cap. $3,0,4 $2,0,4 $7,0, , b(s)=10/-4 $7,0,4 Ob(t) $7,0,4 $3,0,4 3, $1,0,4 32 1,0,4 b(2)=0 b(3)-0 a) Version 1: Find the shortest path from node s to node t. i) Draw the network that corresponds to a circulation problem ii) Provide the formulation for the circulation problem. Enforce one unit of flow on the circulation arc ill) What is the optimal solution to this shortest path problem? Inspection is sufficient. Is the solution unique? b) Version 2: Find the shortest path from node s to every other node cost, min. cap., max. cap $5,0,4 $2.0,4 $1,0,4 $5,0,4 $5,0,40 $3,0,4 .S2,0,4 i) Draw the network that corresponds to a circulation problem ii) Providle the formulation for the circulation problem. (ii) Provide an optimal solution to this shortest path problem by inspection. Problem 5 (12 points) (See: Glover, Klingman, Phillips, p.61) Maze Problem Draw a network corresponding to the following maze: Page 2 of 3 626 words +100% 5045 PM 4x 9/6/2017 Hw 1 2017(1).d0 !Compatibility Mode-word File Insert Design Layout References Mailings Review View Zotera Tell me what you want to d... Home Cut Copy Format Painter Sign in Share Calibri (Body)2- Replace Paste B 1 u . abEx, x' A.,A, A. | TNormal TNO Spac Heading 1 Heading 2 Title Subtitle Subtle Em Emphasis Intense E ,-. Select Clipboard Font Styles Editing Problem 4 (20 points) Formulate the following single source shortest path problem as a circulation problem. b(1) 0 cost, min. cap., max. cap. $3,0,4 $2,0,4 $7,0, , b(s)=10/-4 $7,0,4 Ob(t) $7,0,4 $3,0,4 3, $1,0,4 32 1,0,4 b(2)=0 b(3)-0 a) Version 1: Find the shortest path from node s to node t. i) Draw the network that corresponds to a circulation problem ii) Provide the formulation for the circulation problem. Enforce one unit of flow on the circulation arc ill) What is the optimal solution to this shortest path problem? Inspection is sufficient. Is the solution unique? b) Version 2: Find the shortest path from node s to every other node cost, min. cap., max. cap $5,0,4 $2.0,4 $1,0,4 $5,0,4 $5,0,40 $3,0,4 .S2,0,4 i) Draw the network that corresponds to a circulation problem ii) Providle the formulation for the circulation problem. (ii) Provide an optimal solution to this shortest path problem by inspection. Problem 5 (12 points) (See: Glover, Klingman, Phillips, p.61) Maze Problem Draw a network corresponding to the following maze: Page 2 of 3 626 words +100% 5045 PM 4x 9/6/2017