Index
Help
Created with Snap
Created with Snap
1
1
2
3
-1
4
1
2
3
4
0
0
0
0
eps = 0
4x
.25x
.5x
1x
2x
4x
?
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Edge (1,2) - flow: 0 of 94
Edge (1,4) - flow: 0 of 123
Edge (2,3) - flow: 0 of 127
Edge (4,3) - flow: 0 of 104
Vertex 1 - excess: 1
Vertex 2 - excess: 0
Vertex 3 - excess: -1
Vertex 4 - excess: 0
Edge (2,3)
Vertex 1 - excess: 1
Vertex 2 - excess: 0
Vertex 3 - excess: -1
Vertex 4 - excess: 0
Edge (1,2)
Edge (1,4)
Edge (4,3)
