Algorithms: Maximum flow

It is defined as the maximum amount of flow that the network would allow to flow from source to sink. Multiple algorithms exist in solving the maximum flow problem. Two major algorithms to solve these kind of problems are Ford-Fulkerson algorithm and Dinic's Algorithm. They are explained below.

Ford-Fulkerson Algorithm: It was developed by L. R. Ford, Jr. and D. R. Fulkerson in 1956. A pseudocode for this algorithm is given below,

Inputs required are network graph G, source node S and sink node T.

function: FordFulkerson(Graph G,Node S,Node T): Initialise flow in all edges to 0 while (there exists an augmenting path(P) between S and T in residual network graph): Augment flow between S to T along the path P Update residual network graph return

An augmenting path is a simple path from source to sink which do not include any cycles and that pass only through positive weighted edges. A residual network graph indicates how much more flow is allowed in each edge in the network graph. If there are no augmenting paths possible from S to T, then the flow is maximum. The result i.e. the maximum flow will be the total flow out of source node which is also equal to total flow in to the sink node.

A demonstration of working of Ford-Fulkerson algorithm is shown below with the help of diagrams. Please draw the necessary diagrams to show how the Ford-Fulkerson algorithm works. Consider the network (G), the residual graph ( ) and draw diagrams for all four paths. How would you write the Ford-Fulkerson algorithm in C++? To keep things simple, a graph is represented as a 2D matrix. Include source code comments to the C++ source code.