Skip to content

Instantly share code, notes, and snippets.

@samuelsaari
Last active December 8, 2022 17:24
Show Gist options
  • Save samuelsaari/cb7039bea68693ee7efc6d484f6180f9 to your computer and use it in GitHub Desktop.
Save samuelsaari/cb7039bea68693ee7efc6d484f6180f9 to your computer and use it in GitHub Desktop.
def add_edge(a,b,x):
graph[a][b]+=x
n=5
graph=[[0]*(n+1) for _ in range(n+1)]
seen=[False]*(n+1)
path=[]
result=[]
found=False
min_weight=10**9
# add_edge(1,3,4)
# add_edge(1,2,3)
# add_edge(2,4,8)
# add_edge(3,4,2)
# add_edge(4,5,3)
##############
add_edge(1,2,4)
add_edge(1,3,6)
add_edge(2,3,8)
add_edge(2,4,3)
add_edge(3,5,4)
add_edge(4,5,6)
def print_graph(graph):
for i in range(1,len(graph)):
print(graph[i][1:])
print_graph(graph)
def dfs(x,z):
global found, result
if seen[x]:
return
path.append(x)
seen[x]=True
if x==z and not found:
found=True
result=path[:]
for i in range(1,n+1):
if graph[x][i]>0:
dfs(i,z)
path.pop()
def augment_paths():
global min_weight,graph,result,seen,found,path
while True: #!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
dfs(1,5)
print(result)
print_graph(graph)
if not found: #!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
break
path=[]
seen=[False]*(n+1)
found=False
result=[]
for i in range(len(result)-1):
#print(result[i],result[i+1],graph[result[i]][result[i+1]])
min_weight=min(min_weight, graph[result[i]][result[i+1]])
for i in range(len(result)-1):
graph[result[i]][result[i+1]] -=min_weight
graph[result[i+1]][result[i]] +=min_weight
augment_paths()
print('--')
print_graph(graph)
print(path)
# dfs(1,5)
print(found)
print(result)
# print(min_weight)
# print_graph(graph)
# print(graph)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment