Network flow models describe how material, information, or resources move through a system of nodes and arcs. They are solved using specialized algorithms such as the Ford–Fulkerson method, Edmonds–Karp, and the network simplex method. This page explains how these algorithms work and includes numerical examples with diagrams.

1. Structure of a Network Flow Model

   (s) ----10----> (A) ----5----> (t)
     \                           ^
      \----15----> (B) ----10----/

• Nodes represent locations or stages.
• Arcs represent flow capacity.
• Goal: maximize flow or minimize cost.

2. Max-Flow Using Augmenting Paths

Max-flow problems find the largest possible flow from a source to a sink. The Ford–Fulkerson method repeatedly finds augmenting paths in the residual network.

Numerical Example

(s) --10--> (A) --5--> (t)
(s) --15--> (B) --10-> (t)
(A) --4--> (B)

Step 1: Find augmenting path

Path: s → A → t Capacity = min(10, 5) = 5 Add 5 units of flow.

Step 2: Residual network

(s)->A capacity left: 10 - 5 = 5
(A)->t capacity left: 5 - 5 = 0

Step 3: Next augmenting path

Path: s → B → t Capacity = min(15, 10) = 10 Add 10 units of flow.

Total max flow = 5 + 10 = 15

3. Min-Cost Flow Using Network Simplex

Min-cost flow problems assign costs to arcs and find the cheapest way to send required flow.

Example

Supply at s = 8
Demand at t = 8

Arc costs:
s→A: cost 2, cap 6
s→B: cost 3, cap 6
A→t: cost 4, cap 6
B→t: cost 1, cap 6

Cheapest path: s → A → t Cost = 2 + 4 = 6 per unit Send 6 units (capacity limit).

Remaining demand = 2 units

Next cheapest: s → B → t Cost = 3 + 1 = 4 per unit Send 2 units.

Total cost = 6·6 + 4·2 = 36 + 8 = 44

4. Typical Applications

• Transportation and logistics
• Telecommunications routing
• Production planning
• Assignment and matching problems