Index
Help
Created with Snap
Created with Snap
1
2
3
4
5
6
7
1
2
3
4
5
6
7
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 100
Edge (2,3) - flow: 0 of 150
Edge (3,4) - flow: 0 of 200
Edge (4,5) - flow: 0 of 250
Edge (5,6) - flow: 0 of 300
Edge (6,7) - flow: 0 of 350
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 1
Vertex 2
Vertex 3
Vertex 4
Vertex 5
Vertex 6
Vertex 7
Edge (2,3) - residual capacity: 150
Edge (3,4) - residual capacity: 200
Edge (4,5) - residual capacity: 250
Edge (5,6) - residual capacity: 300
Edge (6,7) - residual capacity: 350
Edge (1,2) - residual capacity: 100
