最大流问题之Ford-Fulkerson算法

Ford-Fulkerson算法（亦即标号法？）的输入与步骤如下：

• 输入
  • 给定一个容量为c的图G=(V, E)，源点s与汇点（终点）t
• 步骤
  1. 对图G中每一个边(u, v)的流量f(u, v)进行初始化为0
  2. 查询过程： 寻找（DFS、深度优先搜索方式）图G中的一条路径p，其中每一条边(u, v) ∈p，都有fc(u, v) = c(u, v) - f(u, v) > 0（c(u, v) 代表当前边的容量，f(u, v) 代表当前边已有的流量，即c(u, v) - f(u, v)代表当前边可用的最大流量，即剩余流量）
  3. 调整过程 ：计算当前路径下每条边的最小剩余容量，cf(p) = min{fc(u, v) : (u, v) ∈p}，然后对于每条边进行如下操作：
     • f(u, v) = f(u, v) + cf(p) （前向狐）
     • f(v, u) = f(v, u) - cf(p) （后向狐）
  4. 往复上述2与3步骤，直至无法找到路径p为止

#!/bin/python
class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v  
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}
 
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result
 
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        for edge in self.get_edges(source):
        return sum(self.flow[edge] for edge in self.get_edges(source))

g = FlowNetwork()
[g.add_vertex(v) for v in "sopqrt"]
g.add_edge('s','o',3)
g.add_edge('s','p',3)
g.add_edge('o','p',2)
g.add_edge('o','q',3)
g.add_edge('p','r',2)
g.add_edge('r','t',3)
g.add_edge('q','r',4)
g.add_edge('q','t',2)
print (g.max_flow('s','t')) #5