the residual graphand edge (vuwas added (uvcannot reappear in the residual graph againunless and until (vuappears in future augmenting path but if it doesthen the distance to at that point must be dv which would be higher than at the time (uvwas previously removed this means that each time (uvreappearsu' distance goes up by this means that any edge can reappear at most | |/ times each augmentation causes some edge to reappear so the number of augmentations is (| || |each step takes (| |)due to the unweighted shortest-path calculationyielding an (| | | |bound on the running time further data structure improvements are possible to this algorithmand there are severalmore complicatedalgorithms long history of improved bounds has lowered the current best-known bound for this problem to (| || |there are also host of very good bounds for special cases for instanceo(| || | / time finds maximum flow in graphhaving the property that all vertices except the source and sink have either single incoming edge of capacity or single outgoing edge of capacity these graphs occur in many applications the analyses required to produce these bounds are rather intricateand it is not clear how the worst-case results relate to the running times encountered in practice relatedeven more difficult problem is the min-cost flow problem each edge has not only capacity but also cost per unit of flow the problem is to findamong all maximum flowsthe one flow of minimum cost both of these problems are being actively researched minimum spanning tree the next problem we will consider is that of finding minimum spanning tree in an undirected graph the problem makes sense for directed graphs but appears to be more difficult informallya minimum spanning tree of an undirected graph is tree formed from graph edges that connects all the vertices of at lowest total cost minimum spanning tree exists if and only if is connected although robust algorithm should report the case that is unconnectedwe will assume that is connected and leave the issue of robustness as an exercise to the reader in figure the second graph is minimum spanning tree of the first (it happens to be uniquebut this is unusualnotice that the number of edges in the minimum spanning tree is | the minimum spanning tree is tree because it is acyclicit is spanning because it covers every vertexand it is minimum for the obvious reason if we need to wire house with minimum of cable (assuming no other electrical constraints)then minimum spanning tree problem needs to be solved for any spanning treetif an edgeethat is not in is addeda cycle is created the removal of any edge on the cycle reinstates the spanning tree property the cost of the spanning tree is lowered if has lower cost than the edge that was removed ifas spanning tree is createdthe edge that is added is the one of minimum cost that avoids creation of cyclethen the cost of the resulting spanning tree cannot be improvedbecause any replacement edge would have cost at least as much as an edge already in the spanning tree this shows that greed works for the minimum spanning tree problem the two algorithms we present differ in how minimum edge is selected