分離パスアルゴリズム

Question

拡張パスを検出する最も簡単な方法は何ですか？ループフィンランドへ、どのようにしながら、

def paths(G, s, t):       # Edge-disjoint path coun 
    H, M, count = tr(G), set(), 0    # Transpose, matching, result 
    while True:        # Until the function returns 
     Q, P = {s}, {}        # Traversal queue + tree 
     while Q:         # Discovered, unvisited 
      u = Q.pop()        # Get one 
      if u == t:        # Augmenting path! 
       count += 1      # That means one more path 
       break        # End the traversal 
      forw = (v for v in G[u] if (u,v) not in M) # Possible new edges 
      back = (v for v in H[u] if (v,u) in M) # Cancellations 
      for v in chain(forw, back):  # Along out- and in-edges 
       if v in P: continue   # Already visited? Ignore 
       P[v] = u       # Traversal predecessor 
       Q.add(v)       # New node discovered 
     else:          # Didn't reach t? 
      return count       # We're donefinnish 

は私を使用することはでき増強パスを検索するための標識越えの使用

カウントエッジ素な道？

Answer 1

私はこれをトリッドして動作しました！

while u != s:  
    u, v = P[u], u 
    if v in G[u]: 
     M.add((u,v)) 
else: 
    M.remove((v,u))