ford fulkerson Algorithm
The Ford-Fulkerson Algorithm is a powerful and widely used method for analyzing and solving network flow problems. It is named after its creators, L.R. Ford Jr. and D.R. Fulkerson, who first introduced the algorithm in 1956. The primary goal of this algorithm is to find the maximum flow in a flow network, which is a directed graph with capacities assigned to its edges. The network consists of a source node, a sink node, and multiple intermediate nodes. The algorithm works by iteratively finding augmenting paths between the source and sink nodes, where the augmenting path represents the potential for increasing flow through the network.
The Ford-Fulkerson Algorithm is based on the idea of residual networks and augmenting paths. The residual network is a derived network that represents the remaining capacity of the original network after considering the current flow. The algorithm starts with an initial flow of zero and iteratively finds an augmenting path in the residual network. Once an augmenting path is found, the flow along this path is increased until the path's capacity is fully utilized. This process is repeated until no more augmenting paths can be found in the residual network, at which point the algorithm terminates, and the maximum flow is obtained. The algorithm's performance is heavily influenced by the choice of augmenting paths, and several variations of the algorithm, such as the Edmonds-Karp and Dinitz algorithms, have been proposed to improve its efficiency.
# Ford-Fulkerson Algorithm for Maximum Flow Problem
"""
Description:
(1) Start with initial flow as 0;
(2) Choose augmenting path from source to sink and add path to flow;
"""
def BFS(graph, s, t, parent):
# Return True if there is node that has not iterated.
visited = [False] * len(graph)
queue = []
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0)
for ind in range(len(graph[u])):
if visited[ind] is False and graph[u][ind] > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return True if visited[t] else False
def FordFulkerson(graph, source, sink):
# This array is filled by BFS and to store path
parent = [-1] * (len(graph))
max_flow = 0
while BFS(graph, source, sink, parent):
path_flow = float("Inf")
s = sink
while s != source:
# Find the minimum value in select path
path_flow = min(path_flow, graph[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parent[v]
return max_flow
graph = [
[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0],
]
source, sink = 0, 5
print(FordFulkerson(graph, source, sink))
