A flow network, also known as a network flow, is a directed graph where each edge has a capacity and each node (except for the source and sink nodes) has a flow value associated with it. Flow networks are commonly used to model transportation or distribution systems, such as water distribution networks, traffic flow, or computer networks.

Fig.An example of flow network with Source and Sink node with capacities of each link

In a flow network:

Nodes: These represent points in the network where the flow can split or merge. Typically, there are two special nodes: a source node, from which flow originates, and a sink node, where flow terminates.
Edges: These represent the connections between nodes and have associated capacities, which indicate the maximum amount of flow that can traverse the edge.
Flow: This is the amount of material, information, or whatever is being transported, that is sent from the source to the sink through the network. The flow must satisfy certain constraints:
- The flow through any edge cannot exceed its capacity.
- The total flow out of any node (except the source and sink) must equal the total flow into that node.

Flow networks are used in optimization problems, such as the maximum flow problem, where the goal is to determine the maximum amount of flow that can be sent from the source to the sink without violating the capacity constraints. They also find applications in various fields including transportation planning, telecommunications, and logistics.

Ford Fulkerson Algorithm

Edmond Karp Algorithm

The algorithm is identical to the Ford–Fulkerson algorithm, except that the search order when finding the augmenting path is defined. The path found must be a shortest path that has available capacity. This can be found by a breadth-first search, where we apply a weight of 1 to each edge. The running time of $O(|V||E|^{2})$ is found by showing that each augmenting path can be found in $O(|E|)$ time, that every time at least one of the $E$ edges becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated edge to the source along the augmenting path must be longer than last time it was saturated, and that the length is at most $|V|$ . Another property of this algorithm is that the length of the shortest augmenting path increases monotonically. There is an accessible proof in Introduction to Algorithms.(THC book).

Push Relabel Algorithm

In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow network. The name “push–relabel” comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a “preflow” and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using push operations under the guidance of an admissible network maintained by relabel operations. In comparison, the Ford–Fulkerson algorithm performs global augmentations that send flow following paths from the source all the way to the sink.

Network Flow/Flow Networks.

Floyd Warshall Algorithm

What is all pair shortest path?

An example of the all-pairs shortest path problem can be illustrated with a simple weighted directed graph representing a road network. Consider the following graph: