Question: what is the total/ OVERALL COMPLEXITY of this code : #https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/ import decimal import time #________________________ford-fulkerson Algorithm---->BFS(graph,2d array,queue)______________________ class Graph: def __init__(self, graph): self.graph =

what is the total/ OVERALL COMPLEXITY of this code :

#https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

import decimal import time #________________________ford-fulkerson Algorithm---->BFS(graph,2d array,queue)______________________

class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph)

def BFS(self, s, t, parent): visited = [False]*(self.ROW) queue = [] queue.append(s) visited[s] = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph[u]): if visited[ind] == False and val > 0: queue.append(ind) visited[ind] = True parent[ind] = u if ind == t: return True return False def FordFulkerson(self, source, sink): parent = [-1]*(self.ROW) 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

c = [[0 for i in range(5000)] for j in range(5000)]

def loadGraph(): my_file = open("/Users/elaff//Algorithm/project/networkdata.txt", "r") for number in my_file: number=number.strip() nums=number.split("\t") row=int(nums[0].strip())-1 col=int(nums[1].strip())-1 c[row][col]=float(nums[2].strip()) loadGraph() s = 0 t = 90 g = Graph(c) start3 = time.perf_counter() f=g.FordFulkerson( s, t) print("Maximum flow: ", f) end3 = time.perf_counter() #o(1) print("time: ",end3 - start3) # o(1)

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!