at all. min_height = ∞ for v in xrange(n): if C[u][v] - F[u][v] > 0: min_height = min(min_height, height[v]) height[u] = min_height + 1 def discharge(u): while excess[u] > 0: if seen[u] < n: # check next neighbour v = seen[u] if C[u][v] - F[u][v] > 0 and height[u] > height[v]: push(u, v) else: seen[u] += 1 else: # we have checked all neighbours. must relabel relabel(u) seen[u] = 0 height[source] = n # longest path from source to sink is less than n long excess[source] = ∞ # send as much flow as possible to neighbours of source for v in range(n): push(source, v) p = 0 while p < len(nodelist): u = nodelist[p] old_height = height[u] discharge(u) if height[u] > old_height: nodelist.insert(0, nodelist.pop(p)) # move to front of list p = 0 # start from front of list else: p += 1 return sum(F[source]) References Network flow problem Graph algorithms