1

質問に飛び込む前に、私がすでに持っているものの背景情報をいくつか示します。

-最初に、エッジの重みが計算された距離である米国中の都市に基づいて、無向隣接行列グラフを作成しました (距離式によって達成されました)。

-Prim のアルゴリズムを使用して、最小スパニング ツリーも実装しました。

今、私が持っている Edmonds Karp 最大フロー アルゴリズムを実装する必要がありますが、次のコードで使用されるアルゴリズムを実装するために、私が持っているデータに基づいて容量グラフを作成する方法について混乱しています:

def edmonds_karp(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for i in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    while True:
        path = bfs(C, F, source, sink)
        if not path:
            break
        # traverse path to find smallest capacity
        flow = min(C[u][v] - F[u][v] for u,v in path)
        # traverse path to update flow
        for u,v in path:
            F[u][v] += flow
            F[v][u] -= flow
    return sum(F[source][i] for i in xrange(n))

def bfs(C, F, source, sink):
    queue = [source]                 
    paths = {source: []}
    while queue:
        u = queue.pop(0)
        for v in xrange(len(C)):
            if C[u][v] - F[u][v] > 0 and v not in paths:
                paths[v] = paths[u] + [(u,v)]
                if v == sink:
                    return paths[v]
                queue.append(v)
    return None

どんな助けでも大歓迎です、ありがとう!

4

1 に答える 1

1

Edmonds-Karp アルゴリズムで行う必要があるのは、すべてのエッジの重みを 1 に変更することだけです。これは、この問題で都市間のエッジ接続を見つけるために必要ではないためです。そして、辺の重みが 1 の都市のグラフが私のキャパシティ グラフになります。また、Edmonds-Karp アルゴリズムには、有向グラフが必要です。

于 2012-12-03T15:23:27.273 に答える