👀 Views: 80 💬 Answers: 1 📅 Created: 2025-06-09

algorithm python ford-fulkerson Python

I'm maintaining legacy code that I'm relatively new to this, so bear with me. I'm trying to implement the Ford-Fulkerson algorithm to find the maximum flow in a flow network using Python, but I'm encountering an issue where the calculated flow is consistently lower than expected. I’ve set up my graph as an adjacency list and a capacity dictionary to keep track of the edge capacities. However, when I run my algorithm, the maximum flow is returning an incorrect value, and I suspect it's related to how I’m updating the flow values. Here’s a simplified version of my implementation: ```python from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(dict) def add_edge(self, u, v, capacity): self.graph[u][v] = capacity self.graph[v][u] = 0 # Initialize reverse flow to 0 def bfs(self, source, sink, parent): visited = {key: False for key in self.graph} queue = [source] visited[source] = True while queue: u = queue.pop(0) for v in self.graph[u]: if not visited[v] and self.graph[u][v] > 0: if v == sink: parent[v] = u return True queue.append(v) visited[v] = True parent[v] = u return False def ford_fulkerson(self, source, sink): parent = {} # Store the path max_flow = 0 while self.bfs(source, sink, parent): path_flow = float('Inf') s = sink while s != source: path_flow = min(path_flow, self.graph[parent[s]][s]) s = parent[s] max_flow += path_flow v = sink while v != source: u = parent[v] self.graph[u][v] -= path_flow self.graph[v][u] += path_flow v = parent[v] return max_flow # Example usage: if __name__ == '__main__': g = Graph() g.add_edge(0, 1, 16) g.add_edge(0, 2, 13) g.add_edge(1, 2, 10) g.add_edge(1, 3, 12) g.add_edge(2, 1, 4) g.add_edge(2, 4, 14) g.add_edge(3, 2, 9) g.add_edge(3, 5, 20) g.add_edge(4, 3, 7) g.add_edge(4, 5, 4) print('The maximum possible flow is:', g.ford_fulkerson(0, 5)) ``` When I run this code, it outputs `The maximum possible flow is: 23`, but I believe the correct answer should be 20. I’ve double-checked my edge capacities and ensured that I'm correctly updating the flow in both directions, but I still can’t figure out where the logic might be going awry. Has anyone encountered a similar issue, or could anyone suggest what I might be overlooking? Any help would be appreciated! This is part of a larger service I'm building. Any ideas what could be causing this?