graph algorithms figure the classic bad case for augmenting is no guarantee that this will be efficient in particularif the capacities are all integers and the maximum flow is fthensince each augmenting path increases the flow value by at least stages sufficeand the total running time is ( *| |)since an augmenting path can be found in (| |time by an unweighted shortest-path algorithm the classic example of why this is bad running time is shown by the graph in figure the maximum flow is seen by inspection to be , , by sending , , down each side random augmentations could continually augment along path that includes the edge connected by and if this were to occur repeatedly , , augmentations would be requiredwhen we could get by with only simple method to get around this problem is always to choose the augmenting path that allows the largest increase in flow finding such path is similar to solving weighted shortest-path problemand single-line modification to dijkstra' algorithm will do the trick if capmax is the maximum edge capacitythen one can show that (|elog capmax augmentations will suffice to find the maximum flow in this casesince (|elog | |time is used for each calculation of an augmenting patha total bound of (| | log |vlog capmax is obtained if the capacities are all small integersthis reduces to (| | log | |another way to choose augmenting paths is always to take the path with the least number of edgeswith the plausible expectation that by choosing path in this mannerit is less likely that smallflow-restricting edge will turn up on the path with this ruleeach augmenting step computes the shortest unweighted path from to in the residual graphso assume that each vertex in the graph maintains dv representing the shortest-path distance from to in the residual graph each augmenting step can add new edges into the residual graphbut it is clear that no dv can decreasebecause an edge is added in the opposite direction of an existing shortest path each augmenting step saturates at least one edge suppose edge (uvis saturatedat that pointu had distance du and had distance dv du then (uvwas removed from