This is a type of Network Optimisation Problem. It may arise in different contexts:
- Networks: Routing as many packets as possible on a given Network.
- Transportation: Sending as many trucks as possible where roads have limits on the number of trucks per unit time.
- Bridges: destroying (?!) some bridges to disconnect s from t while minimising the cost of destroying the bridges.
This problem includes finding a feasible flow through a single source, single sink flow network that is maximum.
Given: A directed graph G(V, E), where each edge is associated with a capacity c(e) > 0. There are two special nodes source 's' and sink 't' (s ≠ t)
Problem: Maximise the total amount of flow from s to t subject to two constraints:
- Flow on an edge e does not exceed c(e).
- Foe every node v ≠ s,t, incoming flow is equal to outgoing flow.
There are two efficient Algorithms: