graph algorithms simple maximum-flow algorithm first attempt to solve the problem proceeds in stages we start with our graphgand construct flow graph gf gf tells the flow that has been attained at any stage in the algorithm initially all edges in gf have no flowand we hope that when the algorithm terminatesgf contains maximum flow we also construct graphgr called the residual graph gr tellsfor each edgehow much more flow can be added we can calculate this by subtracting the current flow from the capacity for each edge an edge in gr is known as residual edge at each stagewe find path in gr from to this path is known as an augmenting path the minimum edge on this path is the amount of flow that can be added to every edge on the path we do this by adjusting gf and recomputing gr when we find no path from to in gr we terminate this algorithm is nondeterministicin that we are free to choose any path from to tobviously some choices are better than othersand we will address this issue later we will run this algorithm on our example the graphs below are ggf gr respectively keep in mind that there is slight flaw in this algorithm the initial configuration is in figure there are many paths from to in the residual graph suppose we select sbdt then we can send two units of flow through every edge on this path we will adopt the convention that once we have filled (saturatedan edgeit is removed from the residual graph we then obtain figure nextwe might select the path sactwhich also allows two units of flow making the required adjustments gives the graphs in figure the only path left to select is sadtwhich allows one unit of flow the resulting graphs are shown in figure the algorithm terminates at this pointbecause is unreachable from the resulting flow of happens to be the maximum to see what the problem issuppose that with our initial graphwe chose the path sadt this path allows three units of flow and thus seems to be good choice the result of this choicehoweverleaves only one path from to in the residual graphit allows one more unit of flowand thusour algorithm has figure initial stages of the graphflow graphand residual graph