which we define by gx (vex)where ex is set of residual edges corresponding to the feasible solution notes what is exwe replace each arc ( ,jin by two arcs ( , )( , )the arc ( ,jhas (residualcapacity rij uij xijand the arc ( ,ihas (residualcapacity rji=xij then we construct the set ex from the new edges with positive residual capacity in the worst case both improved and unimproved algorithms will perform ( augmentationsif norman zadeh developed some examples on which this running time is based using his ideas we compose somewhat simpler network on which the algorithms have to perform ( augmentations and which is not dependent on choice of next path figure worst case example for the shortest augmenting path algorithm all vertexes except and are divided into four subsetss={ ,sk} ={ ,tk} ={ , pand ={ , pboth sets and contain nodes while both sets and contain nodes and are fixed integers each bold arc (connecting and thas unit capacity each dotted arc has an infinite capacity other arcs (which are solid and not straighthave capacity firstthe shortest augmenting path algorithm has to augment flow time along paths (ssttwhich have length equal to the capacities of these paths are unit after that the residual network will contain reversal arcs (tsand the algorithm will chose another augmenting paths (su tsv tof length then the algorithm will have to choose paths (su stv tof length and so on now let' calculate the parameters of our network the number of vertexes is the number of edges is pk as it easy to seethe number of augmentations is ( lovely professional university