최대 흐름 - Ford-Fulkerson : 방향이 지정되지 않은 그래프

Question

Ford-Fulkerson 알고리즘을 사용하여 그래프의 최대 흐름 문제를 해결하려고합니다. 알고리즘은 유향 그래프로만 설명됩니다. 그래프의 방향이 바뀌면 어떨까요?

무 방향성 그래프를 모방하기 위해 수행 한 작업은 한 쌍의 정점 사이에서 두 개의 지향 에지를 사용하는 것입니다. 나를 혼란스럽게하는 것은 다음과 같습니다. 이러한 각 모서리에 잔여 가장자리가 있거나 "반대"방향 가장자리에 나머지 가장자리가 있습니까?

나는 마지막으로 생각했지만 알고리즘은 무한 루프에있는 것처럼 보입니다. 당신 중 누구라도 나에게 도움이되기를 바랍니다. 아래는 내 자신의 구현입니다. find에서 DFS를 사용하고 있습니다.

import sys 
import fileinput 

class Vertex(object): 
    def __init__(self, name): 
     self.name = name 
     self.edges = [] 

    def find(self, sink, path): 
     if(self == sink): 
      return path 
     for edge in self.edges: 
      residual = edge.capacity - edge.flow 
      if(residual > 0 or edge.inf): 
       if(edge not in path and edge.oppositeEdge not in path): 
        toVertex = edge.toVertex 
        path.append(edge) 
        result = toVertex.find(sink, path) 
        if result != None: 
         return result 

class Edge(object): 
    def __init__(self, fromVertex, toVertex, capacity): 
     self.fromVertex = fromVertex 
     self.toVertex = toVertex 
     self.capacity = capacity 
     self.flow = 0 
     self.inf = False 
     if(capacity == -1): 
      self.inf = True 
    def __repr__(self): 
     return self.fromVertex.name.strip() + " - " + self.toVertex.name.strip() 

def buildGraph(vertices, edges): 
    for edge in edges: 
     sourceVertex = vertices[int(edge[0])] 
     sinkVertex = vertices[int(edge[1])] 
     capacity = int(edge[2]) 
     edge1 = Edge(sourceVertex, sinkVertex, capacity) 
     edge2 = Edge(sinkVertex, sourceVertex, capacity) 
     sourceVertex.edges.append(edge1) 
     sinkVertex.edges.append(edge2) 
     edge1.oppositeEdge = edge2 
     edge2.oppositeEdge = edge1 

def maxFlow(source, sink): 
    path = source.find(sink, []) 
    while path != None: 
     minCap = sys.maxint 
     for e in path: 
      if(e.capacity < minCap and not e.inf): 
       minCap = e.capacity 

     for edge in path: 
      edge.flow += minCap 
      edge.oppositeEdge.flow -= minCap 
     path = source.find(sink, []) 

    return sum(e.flow for e in source.edges) 

vertices, edges = parse() 
buildGraph(vertices, edges) 
source = vertices[0] 
sink = vertices[len(vertices)-1] 
maxFlow = maxFlow(source, sink) 

Answer 1

두 개의 반 평행선을 사용하는 접근 방식이 효과적입니다. 가장자리가 a->b 인 경우 (용량 10, 우리가 7을 보내면) 잔여 용량 17이있는 b에서 a 사이의 잔여 가장자리가 생깁니다. 잔여 가장자리는 a에서 b까지 잔량이 3입니다.

원본 백 - 에지 (b에서 a까지)는 그대로 두거나 새로운 잔여 에지와 원래의 백 업을 한쪽 가장자리로 녹일 수 있습니다.

원래 백 - 에지에 잔여 용량을 추가하는 것이 조금 더 간단하지만 확실하지는 않습니까?