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.

Problem Edit

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:

  1. Flow on an edge e does not exceed c(e).
  2. Foe every node v ≠ s,t, incoming flow is equal to outgoing flow.

Algorithms Edit

There are two efficient Algorithms:

  1. Ford-Fulkerson Algorithm
  2. Dinic's Algorithm

See also Edit