[FEATURE REQUEST] Add Dinic's Algorithm to the Graph Algorithms

[ni-ms]

What would you like to Propose?

I would like to propose adding an implementation of Dinic's Algorithm to the graph module. It is an efficient technique for solving maximum flow problems in directed graphs using a layered BFS along with a DFS blocking flow. It performs better than Ford-Fulkerson and Edmonds-Karp in many cases.

Issue details

Dinic’s Algorithm

1. Start with a directed graph

   • Each edge has a capacity (how much flow it can carry).
   • Given a source node s and a sink node t.

2. Build a level graph using BFS

   • This graph only keeps edges that go from one layer to the next (level i to level i+1).
   • It focuses only on the shortest paths from s to t, skipping the inefficient ones.

3. Find a blocking flow using DFS

   • Try to push flow from s to t through the level graph.
   • Stop when every path hits a full edge (no more flow can be pushed).

4. Repeat the process

   • Rebuild the level graph and find another blocking flow.
   • Keep doing this until the BFS can’t reach the sink anymore (no more flow is possible).

5. Return the total flow

   • Add up all the flow pushed from s to t across all iterations.
   • That is maximum flow

References:
https://cp-algorithms.com/graph/dinic.html
https://en.wikipedia.org/wiki/Dinic%27s_algorithm

Additional Information

No response

[gr8swati]

Hi @ni-ms , I’d like to work on this issue and add the Java implementation of Dinic’s Algorithm with proper documentation and test cases.
I’ve previously implemented several graph algorithms like BFS, DFS, and Edmonds–Karp, so I’m confident in extending the module with Dinic’s approach.
I’ll ensure clean, well-commented code following the repository’s structure.
Could you please assign this issue to me?

[ni-ms]

Hi. I have a working version of the code, but you can suggest any modifications

[RiyaJoshi0103]

Hi Maintainers,
I would like to work on this issue as part of Hacktoberfest 2025.
I’ll make sure to follow the contribution guidelines and write clean, well-documented Java code.
Thank you!

[gr8swati]

Hi @ni-ms. I have a working version of the code, but you can suggest any modifications

Thanks, @ni-ms. That’s great to hear. If your implementation is already complete, I’d be happy to:
Review the existing code for readability, efficiency, and edge cases.
Improve or add Javadoc-style documentation for clarity.
Enhance test coverage with additional graph scenarios and corner cases.
Suggest optimizations in BFS/DFS or data structures used for better performance.
Add example usage and comments to help other contributors understand the flow.
Please let me know if I can assist or co-contribute in any of these areas.

[ni-ms]

Hey @SamXop123 , Thanks for the submission! Didn't get a chance to check and submit my version, but your implementation looks great!