Dinic's Algorithm in C

[Kumar-laxmi]

Feature = Dinic's Algorithm in C

• It has been already implemented in C++, Java and Python but is missing in C.

Dinic's algorithm is a graph algorithm used to find the maximum flow in a flow network. Given a directed graph with a source vertex, a sink vertex, and capacities assigned to the edges, the algorithm determines the maximum amount of flow that can be sent from the source to the sink.

It can handle large flow networks efficiently and is considered one of the fastest maximum flow algorithms.

Approach :

1. Initialization:

   • Assign initial flow of zero to all edges in the graph.
   • Create a level graph by performing a Breadth-First Search (BFS) from the source vertex. The level graph indicates the shortest distance from the source to each vertex in terms of the number of edges.

2. Blocking Flow:

   • While there exists a blocking flow (a path from the source to the sink in the level graph):
   • Use Depth-First Search (DFS) to find an augmenting path from the source to the sink in the level graph.
   • Determine the maximum possible flow that can be sent through the augmenting path. Update the flow values of the edges along the augmenting path.

3. Update Level Graph:

   • After each blocking flow is found, update the level graph by performing another BFS from the source.
   • The new level graph reflects the shortest distances from the source considering the updated flow values.

4. Termination and Maximum Flow:

   • When there are no more blocking flows in the level graph, the algorithm terminates.
   • The maximum flow in the network is the sum of the flows leaving the source vertex.

Additional context

[hlw-aryan]

@Kumar-laxmi pls assign this to me

[Kumar-laxmi]

Assigned! @hlw-aryan : C

[shivam0277]

please assign this issue to me i would like to work on this .

[Ashish1100]

Hi @Kumar-laxmi, this is Ashish. This Dinic's Algorithm can be optimized. Here is my optimized approach:

--> Using multiple DFS searches in parallel, this can be done by dividing the level graph into several subgraphs and then running a DFS search on each subgraph in parallel. This can significantly speed up the algorithm, especially for large graphs.

--> The level graph can be implemented using a binary heap, which can significantly speed up the BFS searches.

--> The flow values can be implemented using a bitvector, which can significantly reduce the amount of space required by the algorithm.

You can kindly assign me the issue so that I can work on it.

[github-actions[bot]]

Stale issue message