Index
Help
Created with Snap
Created with Snap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4x
.25x
.5x
1x
2x
4x
?
s = PickSource()
t = PickSink()
InitPotential(s,t)
for
v
in
G.Neighborhood(s):
flow[(s,v)] = cap((s,v))
feasible = False
while
not
feasible:
pushed = False
v = FindExcessVertex()
if
not
v:
feasible = True
else
:
for
u
in
Neighborhood(v):
if
pot[v] > pot[u]:
delta = Min(res((v,u)),excess(v))
if
ForwardEdge(v,u):
flow[(v,u)] = flow[(v,u)] + delta
else
:
flow[(u,v)] = flow[(u,v)] - delta
pushed = True
break
if
not
pushed:
pot[v] = minResNeighborPot(v) + 1
ShowCut(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Edge (1,2) - flow: 0 of 10
Edge (2,3) - flow: 0 of 10
Edge (3,4) - flow: 0 of 10
Edge (4,5) - flow: 0 of 10
Edge (5,6) - flow: 0 of 10
Edge (6,11) - flow: 0 of 1
Edge (6,10) - flow: 0 of 1
Edge (6,9) - flow: 0 of 1
Edge (6,8) - flow: 0 of 1
Edge (6,7) - flow: 0 of 1
Edge (6,12) - flow: 0 of 1
Edge (6,13) - flow: 0 of 1
Edge (6,14) - flow: 0 of 1
Edge (6,15) - flow: 0 of 1
Edge (7,16) - flow: 0 of 1
Edge (8,16) - flow: 0 of 1
Edge (9,16) - flow: 0 of 1
Edge (10,16) - flow: 0 of 1
Edge (11,16) - flow: 0 of 1
Edge (12,16) - flow: 0 of 1
Edge (13,16) - flow: 0 of 1
Edge (14,16) - flow: 0 of 1
Edge (15,16) - flow: 0 of 1
Vertex 1 - excess: 0
Vertex 2 - excess: 0
Vertex 3 - excess: 0
Vertex 4 - excess: 0
Vertex 5 - excess: 0
Vertex 6 - excess: 0
Vertex 7 - excess: 0
Vertex 8 - excess: 0
Vertex 9 - excess: 0
Vertex 10 - excess: 0
Vertex 11 - excess: 0
Vertex 12 - excess: 0
Vertex 13 - excess: 0
Vertex 14 - excess: 0
Vertex 15 - excess: 0
Vertex 16 - excess: 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 7
Vertex 8
Vertex 9
Vertex 10
Vertex 11
Vertex 12
Vertex 13
Vertex 14
Vertex 15
Vertex 16
Edge (5,6) - residual capacity: 10
Edge (4,5) - residual capacity: 10
Edge (3,4) - residual capacity: 10
Edge (2,3) - residual capacity: 10
Edge (1,2) - residual capacity: 10
Edge (6,11) - residual capacity: 1
Edge (6,10) - residual capacity: 1
Edge (6,9) - residual capacity: 1
Edge (6,8) - residual capacity: 1
Edge (6,7) - residual capacity: 1
Edge (6,12) - residual capacity: 1
Edge (6,13) - residual capacity: 1
Edge (6,14) - residual capacity: 1
Edge (6,15) - residual capacity: 1
Edge (7,16) - residual capacity: 1
Edge (8,16) - residual capacity: 1
Edge (9,16) - residual capacity: 1
Edge (10,16) - residual capacity: 1
Edge (11,16) - residual capacity: 1
Edge (12,16) - residual capacity: 1
Edge (13,16) - residual capacity: 1
Edge (14,16) - residual capacity: 1
Edge (15,16) - residual capacity: 1