フォード・ファルカーソン法とその応用 - アルゴリズムクイックリファレンス８章の補足 - ref: http://qiita.com/sasanquaneuf/items/14a4c6459813abf6ccbd

definition.py

# パスの一覧を取得する…結果はコスト、辺のリスト、係数のリスト
def getAllPath(edges, visited, f, t, r, c, e, a):
    if f == t:
        r.append((c,e,a))
    for k in neighbor[f].keys():
        if k not in visited:
            getAllPath(edges, visited + [f], k, t, r, c + neighbor[f][k][2], e + [neighbor[f][k][1]], a + [neighbor[f][k][0]])

# パスに対して「今そのパスが取れる最大の値」を返す
def getMaximalFlow(world, (c,e,a)):
    l = len(e)
    delta = float("inf")
    for i in range(0, l):
        if a[i] > 0:
            if delta > world[e[i]][0] - world[e[i]][1]:
                delta = world[e[i]][0] - world[e[i]][1]
        elif a[i] < 0:
            if delta > world[e[i]][1]:
                delta = world[e[i]][1]
        else:
            delta = 0
    return delta

# グラフを更新する
def updateWorld(world, (c,e,a), delta):
    l = len(e)
    for i in range(0, l):
        world[e[i]] = (world[e[i]][0], world[e[i]][1] + a[i] * delta)

drawGraphy.py

# 可視化
import networkx as nx
import matplotlib.pyplot as plt
import math

G = nx.DiGraph()
srcs, dests = zip(* [(fr, to) for (fr, to) in world.keys()])
G.add_nodes_from(srcs + dests)

for (s,r,(d,c)) in edges:
    G.add_edge(s, r, weight=20/math.sqrt(d))

# 位置、微調整する
pos = {"A'"  : ([-0.55,0]),
       'A'  : ([0.25,0]),
       'B1' : ([1,-1.2]),
       'B2' : ([1,0]),
       'B3' : ([1,1.2]),
       'C1' : ([2,-1.2]),
       'C2' : ([2,0]),
       'C3' : ([2,1.2]),
       'D' : ([2.8,0]),
      }

edge_labels=dict([((f,t,),str(world[(f,t)][1]) + '/' + str(world[(f,t)][0]) )
             for (f,t) in world.keys()]) # 辺のラベル、適当に変える

plt.figure(1)
nx.draw_networkx(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels,label_pos=0.74) # これも適当に調整

plt.axis('equal')
plt.show()

solve.py

neighbor = {}
world = {}
for (f,t,(v,c)) in edges:
    # コスト用辞書
    if not f in neighbor.keys():
        neighbor[f] = {}
    neighbor[f][t] = (1,(f,t),c) # 重み係数、基底、コスト
    if not t in neighbor.keys():
        neighbor[t] = {}
    neighbor[t][f] = (-1,(f,t),-c) # 重み係数、基底、コスト
    # 現在値格納用辞書
    world[(f,t)] = (v,0) # 最大値、現在値

r = []
getAllPath(edges,[],"A'",'D',r,0,[],[])
r.sort()

l = len(r)
i = 0
while i < l:
    delta = getMaximalFlow(world, r[i])
    if delta > 0:
        updateWorld(world, r[i], delta)
        i = 0
    else:
        i = i + 1

world

データ

edges = {("A'", 'A', (100, 0)),
 ('A', 'B1', (100, 10)),('A', 'B2', (100, 5)),('A', 'B3', (100, 6)),
 ('B1', 'C1', (11, 5)),('B1', 'C2', (10, 9)),('B1', 'C3', (14, 5)),
 ('B2', 'C1', (17, 9)),('B2', 'C2', (12, 6)),('B2', 'C3', (20, 7)),
 ('B3', 'C1', (13, 7)),('B3', 'C2', (11, 6)),('B3', 'C3', (13, 10)),
 ('C1', 'D', (100, 0)),('C2', 'D', (100, 0)),('C3', 'D', (100, 0))}

結果

{('A', 'B1'): (100, 25), ('A', 'B2'): (100, 49), ('A', 'B3'): (100, 26),
 ("A'", 'A'): (100, 100),
 ('B1', 'C1'): (11, 11), ('B1', 'C2'): (10, 0), ('B1', 'C3'): (14, 14),
 ('B2', 'C1'): (17, 17), ('B2', 'C2'): (12, 12), ('B2', 'C3'): (20, 20),
 ('B3', 'C1'): (13, 13), ('B3', 'C2'): (11, 11), ('B3', 'C3'): (13, 2),
 ('C1', 'D'): (100, 41), ('C2', 'D'): (100, 23), ('C3', 'D'): (100, 36)}