편협한 경로 알고리즘

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 

내가 I를 사용할 수 및 증가 경로를 찾기 라벨링 순회를 사용

계산 에지 연결되지 않은 경로?

Answer 1

나는 이것을 사용하고 효과가 있었다!

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