Ford-Fulkerson Max Flow

Problem

Compute the maximum flow from node s to node t in a directed capacitated network with Ford-Fulkerson using DFS augmenting paths.

edges is a list of [u, v, capacity] triples with integer capacities. Maintain a residual capacity matrix, push flow along any path with spare capacity, and return the total flow value.

Hint

Residual reverse edges allow the algorithm to undo earlier routing decisions.

Test cases

case 1

in: [4,[[0,1,3],[0,2,2],[1,2,5],[1,3,2],[2,3,3]],0,3]

expected: 5

case 2

in: [3,[[0,1,1],[1,2,1]],0,2]

expected: 1

case 3

in: [3,[[0,1,5]],0,2]

expected: 0

case 4

in: [4,[[0,1,10],[0,2,10],[1,2,1],[1,3,10],[2,3,10]],0,3]

expected: 20

case 5

in: [2,[[0,1,7],[1,0,3]],0,1]

expected: 7

Starter codePython

def max_flow(n, edges, s, t):
    # Your code here
    pass

5 test cases · run your code against them in the editor