Push Relabel Algorithm

Push relabel algorithm is also known as Preflow Push algorithm. It is used for computing maximum flows in a flow network.

Maximum flow in a network graph

In a network graph where every edge has a given capacity, maximum flow is defined as the maximum amount of flow that can move from source to sink. Maximum flow is calculated keeping in mind two constraints,

For every vertex (except source and sink), incoming flow is equal to outgoing flow.
Flow of an edge shouldn't exceed its capacity.

Concep...