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

Maximum Flow (Dinic) · Nhóm: Đồ thị

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

Mã Python

def dinic(adj, s, t):
    flow = 0
    while True:
        # 1) BFS level graph from source
        level = bfs_levels(adj, s)
        if level[t] < 0:
            break            # sink unreachable: done
        # 2) push blocking flow on level graph
        it = [0] * n
        while True:
            pushed = dfs(s, INF, t, level, it, adj)
            if pushed == 0:
                break
            flow += pushed
    return flow

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