Mô phỏng thuật toán Luồng cực đại (Edmonds-Karp)

Maximum Flow (Edmonds-Karp) · Nhóm: Đồ thị

Luồng cực đại (Edmonds-Karp) (Maximum Flow (Edmonds-Karp)), nhóm Đồ thị.

Mã Python

def max_flow(cap, s, t):
    total = 0
    while True:
        prev = bfs_augmenting(cap, s, t)
        if t not in prev:
            break
        path = rebuild(prev, s, t)
        bottleneck = min(cap[u][v] for u, v in path)
        for u, v in path:
            cap[u][v] -= bottleneck
            cap[v][u] += bottleneck
        total += bottleneck
    return total

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.