Max flow

Question 1

Describe the max-flow problem.

Answer 1

Given a weighted, directed graph with a source (Node with no edges in, only out) and a sink (Node with no edges out, only in), what is the maximum number of units we can send from the source to the sink?

Question 2

How do you solve the max-flow problem?

Answer 2

Use BFS to find a path between source and sink. Prioritize moving to nodes with lower index numbers with positive excess capacity.

Once found, identify the edge with the lowest excess capacity. Subtract this much from the excess each edge in the path.

Repeat this until there are no existing paths from the source to the sink.