最大流量 - Ford-Fulkerson：無向圖

Question

我正在嘗試使用Ford-Fulkerson算法解決圖形的最大流量問題。該算法僅用有向圖來描述。什麼時候該圖是無向的？

我所做的模仿無向圖的方法是在一對頂點之間使用兩個有向邊。令我困惑的是：這些邊緣中的每一個邊緣是否應該有殘留邊緣，或者是否爲「相反」有向邊緣？

我假設了最後一次，但我的算法似乎進入了一個無限循環。我希望你們中的任何人都能給我一些幫助。以下是我自己的實現。我在查找中使用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），我們引入一個新的殘留邊緣（從b到a，剩餘容量爲17，剩餘邊緣從a到b有剩餘容量3）。

原始的後緣（從b到a）可以保持原樣，或者新的殘留邊緣和原始的後緣可以融合成一個邊緣。

我可以想象，將殘餘容量添加到原始的後端更簡單一些，但不確定。