Algorithm - Path Decomposition

Compute max flow from $s = 1$ to $t = n$ with unit capacities. Flow_value = max flow For $i = 1$ to flow_value: path = [] current = $s$ While current $eq t$: Find any edge $(current, next)$ with flow $> 0$.

Add $(current, next)$ to path. Decrease flow on $(current, next)$ by $1$. Current = next Add path to result.

Output flow_value and all paths. Each iteration extracts one path and removes it from the flow.