FordFulkerson algorithm¶
The FordFulkerson algorithm finds the maximum flow in a graph.
The algorithm begins with an empty flow, and at each step finds a path from the source to the sink that generates more flow.
Finally, when the algorithm cannot increase the flow anymore, the maximum flow has been found.
The algorithm uses a special representation of the graph where each original edge has a reverse edge in another direction.
The weight of each edge indicates how much more flow we could route through it.
At the beginning of the algorithm, the weight of each original edge equals the capacity of the edge and the weight of each reverse edge is zero.
Algorithm description¶
The FordFulkerson algorithm consists of several rounds.
On each round, the algorithm finds a path from the source to the sink such that each edge on the path has a positive weight.
If there is more than one possible path available, we can choose any of them.
After choosing the path, the flow increases by $x$ units, where $x$ is the smallest edge weight on the path.
In addition, the weight of each edge on the path decreases by $x$ and the weight of each reverse edge increases by $x$.
The idea is that increasing the flow decreases the amount of flow that can go through the edges in the future.
On the other hand, it is possible to cancel flow later using the reverse edges of the graph if it turns out that it would be beneficial to route the flow in another way.
The algorithm increases the flow as long as there is a path from the source to the sink through positiveweight edges.
If It is not possible to increase the flow anymore, because there is no path from the source to the sink with positive edge weights, the algorithm terminates and has found the maximum flow.
Finding paths¶
The FordFulkerson algorithm does not specify how we should choose the paths that increase the flow.
In any case, the algorithm will terminate sooner or later and correctly find the maximum flow.
However, the efficiency of the algorithm depends on the way the paths are chosen.
Path finding techniques¶
In practive, the scaling algorithm is easier to implement, because depthfirst search can be used for finding paths.
Both Algorithms are efficient enough for problems that typically appear in programming contests.
EdmondKarp algorithm¶
The algorithm chooses each path so that the number of edges on the path is as small as possible.
This can be done by using $\text{breadthfirst search}$ instead of depthfirst search for finding paths.
It can be proven that this guarantees that the flow increases quickly, and the time complexity of the algorithm is $\Omicron(m^2n)$.
Scaling algorithm¶
The algorithm uses depthfirst search to find paths where each weight is at least a threshold value.
Initially, the threshold value is some large number, for example the sum of all edge weights of the graph.
Always when a path cannot be found, the threshold value is divided by 2.
The time complexity of the algorithm is $\Omicron(m^2lgc)$, where $c$ is the initial threshold value.
Dinic Algorithm¶
Time complex $\Omicron(EV^2)$
Like EdmondKarp algorithm, Dinic's algorithm uses following concepts

A flow is maximum if there is no $source$ to $sink$ path in residual graph.

$\text{BFS}$ is used in a loop. There is difference though in the way we use BFS in both algorithms.
In Edmond's Karp algorithm, we use $\text{BFS}$ to find a augmenting path and send flow accress this path.
In Dinic's algorithm we use $\text{BFS}$ to check if more flow is possible and to construct level graph.
In, level graph, we assign levels to all nodes, level of a node is shortest distance (in terms of number of edges) of the node from source.
Once level graph is constructed, we send multiple flows using this level graph.
This is the reason it works better than EdmondKarp.
In EdmondKarp, we send only flow that is send across the path found by BFS.
Implementation (Dinic with Scaling)¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 
