АЛГОРИТМ ФОРДА ФАЛКЕРСОНА PYTHON

Алгоритм Форда-Фалкерсона является одним из алгоритмов поиска максимального потока в сети. Этот алгоритм работает на основе увеличивающих путей - путей из источника в сток, максимальный поток которых еще не найден.

Основная идея алгоритма заключается в поочередном нахождении увеличивающего пути и нахождении минимальной пропускной способности этого пути. Используя минимальную пропускную способность, алгоритм увеличивает поток вдоль этого пути.

def ford_fulkerson(graph, source, sink):    max_flow = 0    flow = [[0] * len(graph) for _ in range(len(graph))]    while True:        path = bfs(graph, source, sink, flow)        if not path:            break        min_capacity = float("inf")        for i in range(len(path) - 1):            u, v = path[i], path[i + 1]            capacity = graph[u][v] - flow[u][v]            min_capacity = min(min_capacity, capacity)        for i in range(len(path) - 1):            u, v = path[i], path[i + 1]            flow[u][v] += min_capacity            flow[v][u] -= min_capacity        max_flow += min_capacity    return max_flowdef bfs(graph, source, sink, flow):    queue = [source]    visited = [False] * len(graph)    visited[source] = True    parent = [-1] * len(graph)    while queue:        u = queue.pop(0)        for v in range(len(graph)):            if not visited[v] and graph[u][v] - flow[u][v] > 0:                queue.append(v)                visited[v] = True                parent[v] = u    if not visited[sink]:        return None    path = [sink]    while path[-1] != source:        path.append(parent[path[-1]])    return path[::-1]

Пример использования:

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],]source, sink = 0, 5print(ford_fulkerson(graph, source, sink)) # Output: 23