Index
Help
1
1
2
3
-1
4
1
0
2
0
3
0
4
0
def
AdmissibleEdge(v,eps):
for
w
in
Neighborhood(v):
if
ReducedCosts((v,w)) < 0:
return
(v,w)
return
None
def
ReducedCosts((u,v)):
return
cost[(u,v)] + pot[u] - pot[v]
eps = RecalculateCosts()# for integer eps
while
eps > 1:
for
e
in
Edges():
if
ReducedCosts(e) > 0:
flow[e] = 0
elif
ReducedCosts(e) < 0:
flow[e] = cap(e)
IsFlow = False
while
not
IsFlow:
v = ActiveVertex()
if
v:
e = AdmissibleEdge(v,eps)
if
e:
delta = Min(res(e),excess(v))
if
ForwardEdge(e[0],e[1]):
flow[(e[0],e[1])] = flow[(e[0],e[1])] + delta
else
:
flow[(e[1],e[0])] = flow[(e[1],e[0])] - delta
else
:
Lower(v,eps / 2)
else
:
IsFlow = True
eps = eps / 2