# Max Flow Ford Fulkerson  **Flow Graph** A flow graph (flow network) is a directed graph where each edge has a certain *capacity* which can receive a certain amount of *flow*. The flow running through an edge must be less than or equal to the capacity.  **Max Flow Algorithm** To find the maximum flow the Ford-Fulkerson method repeatedly finds **augmenting paths** through the **residual graph** and *augments the flow* until no more augmenting paths can be found.  **Augmenting Path** An augmenting path is a path of edges in the residual graph with unused capacity greater than zero from the source `s` to the sink `t`. One way of finding an augmented path is [DFS](Graph-Algorithms.md#1%20Depth%20First%20Search%20DFS). Note that every augmenting path will have a *bottleneck* value, which is the smallest (least flow) path along the path.  **Augmenting the Flow** We can use the bottleneck value to augment the flow. Augmenting the flow simply means *updating* the flow values of the edges along the augmenting path. For the forward edges this means increasing the flow by the bottleneck value. Note that when augmenting the flow along the forward edges, we also need to *decrease the flow* along the backwards edges (i.e. the **residual edges**) by the *bottleneck value*. They are shown in the images above as dotted edges.   **Residual Edges** They are the backwards edges in our graph, which exist to "undo" bad augmenting paths which do not lead to a maximum flow. It should be noted that residual edges become valid edges to take when we are trying to find an augmented flow. Consider the screenshot for the residual edge below. The augmenting path that we found (in orange) had 6 as the maximum value of flow that could be pushed along it without exceeding the maximum flow of the minimum edge (i.e. 6). So, all edges had 6 units of flow pushed along them. Now, to reverse this particular path, we would need to simply perform the opposite operation, namely subtracting 6 and walking backward along the path.   **Residual Graph** So, we can think of every edge in the original graph as having a residual edge with a flow and capacity of 0, which is not usually shown. The residual graph is the graph which contains the residual edges. When we talk about the *flow graph* we usually mean the residual graph.    ### Example    ### Key Idea The reason that we can go backwards along edges (i.e. along the residual edges) is because our main objective is to simply ensure that our graph remains in *equilibrium*. ### Complexity  --- Date: 20210517 Keywords: Augmenting paths, augmented flow, flow graph, residual graph Links to: [Graph-Algorithms](Graph-Algorithms.md) References: * [Max Flow Ford Fulkerson - Network Flow](https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=34) * [Ford-Fulkerson in 5 minutes — Step by step example](https://www.youtube.com/watch?v=Tl90tNtKvxs)