Page 286 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

which we defi ne by G = (V, E ), where E is a set of residual edges corresponding to the feasible Notes
x x x
solution x.
What is E ? We replace each arc (i,j) in E by two arcs (i,j), (j,i): the arc (i,j) has (residual) capacity r
ij
x
= u - x , and the arc (j,i) has (residual) capacity r =x . Then we construct the set E from the new
ij ij ji ij x
edges with a positive residual capacity.
In the worst case both improved and unimproved algorithms will perform O(n ) augmentations,
3
if m ~ n . Norman Zadeh developed some examples on which this running time is based. Using
2
his ideas we compose a somewhat simpler network on which the algorithms have to perform
O(n ) augmentations and which is not dependent on a choice of next path.
3
Figure 14.5: Worst Case Example for the Shortest Augmenting Path Algorithm

k

s3 t3

s2 t2
s1 t1

s t

u1 v1

u2 v2
2p
u3 v3

u4 v4

All vertexes except s and t are divided into four subsets: S={s ,...,s }, T={t ,...,t }, U={u ,...,u p} and
k
1
2
1
k
1
V={v ,...,v p}. Both sets S and T contain k nodes while both sets U and V contain 2p nodes. k and
1
2
p are fixed integers. Each bold arc (connecting S and T) has unit capacity. Each dotted arc has an

infinite capacity. Other arcs (which are solid and not straight) have capacity k.

First, the shortest augmenting path algorithm has to augment fl ow k time along paths (s, S, T,
2
t) which have length equal to 3. The capacities of these paths are unit. After that the residual
network will contain reversal arcs (T, S) and the algorithm will chose another k augmenting
2
paths (s, u , u , T, S, v , v , t) of length 7. Then the algorithm will have to choose paths (s, u , u , u ,
1
1
3
2
2
1
2
u , S, T, v , v , v , v , t) of length 11 and so on...
4 4 3 2 1
Now let’s calculate the parameters of our network. The number of vertexes is n = 2k + 4p + 2. The
2
number of edges is m = k + 2pk + 2k + 4p. As it easy to see, the number of augmentations is a =
k (p + 1).
2
LOVELY PROFESSIONAL UNIVERSITY 281