Question
i need an overall time complexity for the *whole* algorithm ------------------------------------------------------------------ import decimal import time #________________________ford-fulkerson Algorithm---->BFS(graph,2d array,queue)______________________ class Graph: def __init__(self, graph): self.graph =
i need an overall time complexity for the *whole* algorithm
------------------------------------------------------------------
import decimal import time #________________________ford-fulkerson Algorithm---->BFS(graph,2d array,queue)______________________
class Graph: def __init__(self, graph): self.graph = graph #o(1) self. ROW = len(graph) #o(1)
def BFS(self, s, t, parent): visited = [False]*(self.ROW) #o(V) queue = [] queue.append(s) #o(1) visited[s] = True #o(1) while queue: u = queue.pop(0) #o(1) for ind, val in enumerate(self.graph[u]): #o(V) if visited[ind] == False and val > 0: #o(1) queue.append(ind) #o(1) visited[ind] = True #o(1) parent[ind] = u #o(1) if ind == t: #o(1) return True return False def FordFulkerson(self, source, sink): parent = [-1]*(self.ROW) #o(V) max_flow = 0 #o(1) while self.BFS(source, sink, parent) :#o(V*(V+E)) path_flow = float("Inf") #o(1) s = sink #o(1) while(s != source): #o(V) path_flow = min (path_flow, self.graph[parent[s]][s]) #o(1) s = parent[s] #o(1) max_flow += path_flow #o(1) v = sink #o(1) while(v != source): #o(V) u = parent[v] #o(1) self.graph[u][v] -= path_flow #o(1) self.graph[v][u] += path_flow #o(1) v = parent[v] #o(1) return max_flow #o(1)
c = [[0 for i in range(5000)] for j in range(5000)] #o(V^2)
def loadGraph(): my_file = open(r"C:\Users\azhar\OneDrive\Documents\algorithms\project\datat.txt") #o(1) for number in my_file: #o(E) number=number.strip() #o(1) nums=number.split("\t") #o(1) row=int(nums[0].strip())-1 #o(1) col=int(nums[1].strip())-1 #o(1) c[row][col]=float(nums[2].strip()) #o(1) loadGraph() #o(E) s = 0 #o(1) t = 90 #o(1) g = Graph(c) #o(1) start3 = time.perf_counter() #o(1) f=g.FordFulkerson( s, t) #o(V*(V+E)+V) 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
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started