Flow network

Question 1

What is a flow network and what is the capacity of each arc?

Answer 1

Weighted, directed graph with nodes s, t where s is the source and t is the destination.
* s has only out neighbours
* t has only in neighbours
Capacity of arc = weight

Question 2

What is the maximal flow problem?

Answer 2

Find max flow F from s -> t subject to:
- flow along arc does not exceed capacity
- Flow into vertex = flow out of vertex

Question 3

What are the 3 variables defined for each arc?

Answer 3

cij = capacity
fij = flow
eij = excess capacity (c - f)

Question 4

How do we find the maximum flow through a network?

Answer 4

Max flow = capacity of min cut

Question 5

What is the goal of the minimum cost flow?

Answer 5

Let dij = unit cost of flow through arc
Goal is to minimise cost (flow * cost) subject to capacity restrictions and total flow = F

Question 6

What are the steps for the minimum cost flow?

Answer 6

1. Initialse total flow G = 0 and cost T = 0
2. Create labels on each arc (f, e, d)
3. P = shortest path from source to sink using cost, p = length of path
4. b minimum of excess capacity on the arcs in P and F-G (flow needed - current flow) (This is the minimum between excess capacity in shortest path and how much flow is still needed to push.)
5. Assign b uunits of flow to each arc in P and add bp to T.