0
創造埃德蒙茲卡普最大流算法容量圖形之前,我潛入這裏的問題是什麼,我已經有一些背景資料:跨越基於城市在Python
-I首先創建了一個非定向鄰接矩陣圖美國的邊緣權重是計算距離(通過距離公式實現的)。
- 我還使用prim算法實現了最小生成樹。
現在我需要實現我有埃德蒙茲卡普最大流量的算法,但我在困惑我會如何創建一個基於我在爲了實現在下面的代碼使用的算法的數據容量圖表:
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
任何幫助將不勝感激,謝謝!