fordfulkerson algorithm for maximum flow problem https en wikipedia orgwikiforde28093fulkersonalgorithm description 1 start with initial flow as 0 2 choose the augmenting path from source to sink and add the path to flow this function returns true if there is a node that has not iterated args graph adjacency matrix of graph source source sink sink parents parent list returns true if there is a node that has not iterated breadthfirstsearchgraph 0 5 1 1 1 1 1 1 true breadthfirstsearchgraph 0 6 1 1 1 1 1 1 traceback most recent call last indexerror list index out of range source node traverse all adjacent nodes of u this function returns the maximum flow from source to sink in the given graph caution this function changes the given graph args graph adjacency matrix of graph source source sink sink returns maximum flow testgraph 0 16 13 0 0 0 0 0 10 12 0 0 0 4 0 0 14 0 0 0 9 0 0 20 0 0 0 7 0 4 0 0 0 0 0 0 fordfulkersontestgraph 0 5 23 this array is filled by breadthfirst search and to store path while there is a path from source to sink find the minimum value in the selected path this function returns true if there is a node that has not iterated args graph adjacency matrix of graph source source sink sink parents parent list returns true if there is a node that has not iterated breadth_first_search graph 0 5 1 1 1 1 1 1 true breadth_first_search graph 0 6 1 1 1 1 1 1 traceback most recent call last indexerror list index out of range mark all nodes as not visited breadth first search queue source node pop the front node traverse all adjacent nodes of u this function returns the maximum flow from source to sink in the given graph caution this function changes the given graph args graph adjacency matrix of graph source source sink sink returns maximum flow test_graph 0 16 13 0 0 0 0 0 10 12 0 0 0 4 0 0 14 0 0 0 9 0 0 20 0 0 0 7 0 4 0 0 0 0 0 0 ford_fulkerson test_graph 0 5 23 this array is filled by breadth first search and to store path while there is a path from source to sink infinite value find the minimum value in the selected path
graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]


def breadth_first_search(graph: list, source: int, sink: int, parents: list) -> bool:
    
    visited = [False] * len(graph)  
    queue = []  

    
    queue.append(source)
    visited[source] = True

    while queue:
        u = queue.pop(0)  
        
        for ind, node in enumerate(graph[u]):
            if visited[ind] is False and node > 0:
                queue.append(ind)
                visited[ind] = True
                parents[ind] = u
    return visited[sink]


def ford_fulkerson(graph: list, source: int, sink: int) -> int:
    
    
    parent = [-1] * (len(graph))
    max_flow = 0

    
    while breadth_first_search(graph, source, sink, parent):
        path_flow = int(1e9)  
        s = sink

        while s != source:
            
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]

        max_flow += path_flow
        v = sink

        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = parent[v]

    return max_flow


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(f"{ford_fulkerson(graph, source=0, sink=5) = }")