Skip to content

Add .py implementation of Ford-Fulkerson Algorithm #57

@priyansh-narang2308

Description

@priyansh-narang2308

Problem: For a directed network, maximize the flow from a designated source node (s) to a designated sink node (t).
Proposed Solution: The Ford-Fulkerson algorithm iteratively finds augmenting paths from s to t with spare capacity in the residual graph. The residual graph keeps track of remaining capacities and permits "undoing" flow via backward edges.
Usess Depth-First Search to find the augmenting paths in a cost-effective manner. If the depth-first search detects the path, increase flow on the forward edges, while decrease flow along backward edges with a given capacity - this means minimum capacity over that particular path. Iterate through these procedures until no further augmenting path is found.
This solution solves a fundamental network flow problem with applications, such as logistics. It gives a good foundation for understanding maximum flow algorithms, such as Edmonds-Karp which uses BFS.

Metadata

Metadata

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions