(A) Consider the following network, where each number along a link repre between

Question

(A) Consider the following network, where each number along a link repre between the pair of nodes connected by that link. The objective is to find the shortest path from origin to the destination. Use dynamic programming to solve this problem by manually constructing the usual tables for n = 3, n = 2 and n-1 sents the actual distance 3. (B) For the network shown below, use the augmenting path algorithm to find the flow pattern giving the maximum flow from the source to the sink, given that the arc capacity from node i to node j Show your work. 8 (d estimation ) Congin) 0 3 4 2- 6 4 (Sink) urce 3

Explanation / Answer

A) We find path distances for all possible path as

Here Shortest path is O-C-E-T

B) We compute all possible flow from the source to sink is as

Here maximum flow is 24 at path 1-2-3-4-6-9.

Path Distance O-A-D-T 9+5+8 = 22 O-B-D-T 7+8+8 = 23 O-B-E-T 7+7+7 = 21 O-C-E-T 6+6+7 = 19

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.