-
Notifications
You must be signed in to change notification settings - Fork 30
Description
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.