Network Flow Algorithm

Let us consider a directed graph G = (V, E), along with special vertices s and t called the source and target. Here, u → v denotes the directed edge from vertex u to vertex v.

If we want to determine the maximum possible transport from one city to another over the connecting roads where roads are unidirectional having limited capacity of transportation, we have to use a network flow algorithm.

Here, we consider the cities as vertices of the graph and roads as edges, where maximum material transport over using the road is the weight of the edge.

Intuitively, the maximum flow problem asks for the largest amount of material that can be transported from one vertex to another; the minimum cut problem asks for the minimum damage needed to separate two vertices.

---

Flow

An (s, t )-flow (or just a flow if the source and target are clear from context) is a function that satisfies the following conservation constraint at every vertex v except possibly s and t:

We say that a flow f is feasible (with respect to c) if f(e) ≤ c(e) for every edge e. Most of the time we will consider only flows that are feasible with respect to some fixed capacity function c. We say that a flow f saturates edge e if f(e) = c(e), and avoids edge e if f(e) = 0. The maximum flow problem is to compute a feasible (s, t)-flow in a given directed graph, with a given capacity function, whose value is as large as possible.

Each edge is labelled with its flow/capacity.

---

Cuts

An (s, t )-cut is a partition of the vertices into disjoint subsets S and T - meaning S ∪ T = V and S ∩ T = φ where s ∈ S and t ∈ T. If we have a capacity function c: E → R, the capacity of a cut is the sum of the capacities of the edges that start in S and ending in T:

|| S, T||:= ∑_v∈S ∑_w∈T c(v → w)

Notice that the definition is asymmetric; edges that start in T and end in S are unimportant. The minimum cut problem is to compute an (s, t)-cut whose capacity is as large as possible.

---

The Max-Flow Min-Cut Theorem

The value of the maximum flow is equal to the capacity of the minimum cut.

Let f be a feasible flow. We define a new capacity function c_f: V x V → R, called the residual capacity, as follows:

cf(u → v)	=	c(u → v) - f(u → v)	if u → v 2 ∈ E
	=	f(v → u)	if v → u ∈ E
	=	0	otherwise

Source code

#include<stdio.h> #include<assert.h> /* maxVertices represents maximum number of vertices that can be present in the graph. */ #define maxVertices 100 #define INF 123456789 /* Input Format: Graph is directed and weighted. First two integers must be number of vertces and edges which must be followed by pairs of vertices which has an edge between them. */ int min(int a,int b) { return (a < b) ? a : b; } void init(int distance[maxVertices][maxVertices]) { int iter, jter; for(iter = 0; iter < maxVertices; iter++) { for(jter = 0; jter < maxVertices; jter++) { if(iter==jter) { distance[iter][jter] = 0; } else { distance[iter][jter] = INF; } } } } void FloydWarshall(int distance[maxVertices][maxVertices], int vertices) { int from, to, via; for(from = 0; from < vertices; from++) { for(to = 0; to < vertices; to++) { for(via = 0; via < vertices; via++) { distance[from][to] = min(distance[from][to], distance[from][via]+distance[via][to]); } } } } int main() { int graph[maxVertices][maxVertices], size[maxVertices] = {0}, visited[maxVertices] = {0}; int distance[maxVertices][maxVertices]; int vertices, edges, iter,j ter; int vertex1, vertex2, weight; /* vertices represent number of vertices and edges represent number of edges in the graph. */ scanf("%d%d", &vertices, &edges); /*initialize distance between all pairs as infinity*/ init(distance); /* Here graph[i][j] represent the weight of edge joining i and j */ for(iter = 0; iter < edges; iter++) { scanf("%d%d%d", &vertex1, &vertex2, &weight); assert(vertex1 >= 0 && vertex1 < vertices); assert(vertex2 >= 0 && vertex2 < vertices); graph[vertex1][vertex2] = weight; distance[vertex1][vertex2] = weight; } FloydWarshall(distance, vertices); for(iter = 0; iter < vertices; iter++) { for(jter = 0; jter < vertices; jter++) { if(distance[iter][jter] >= INF) { printf("The shortest distance between %d and %d is Infinity\n",iter,jter); } else { printf("The shortest distance between %d and %d is %d\n",iter,jter,distance[iter][jter]); } } } return 0; }

Happy Exploring!