1469960
Thuật toán Edmonds–Karp
https://vi.wikipedia.org/wiki?curid=1469960
Title: Thuật toán Edmonds–Karp
Trong cặp số formula_1 trên mỗi cung, formula_2 là luồng hiện tại, và formula_3 khả năng thông qua. Khả năng thông qua còn dư từ formula_4 đến formula_5 là formula_6, hiệu của khả năng thông qua và luồng hiện tại. Nếu luồng từ formula_4 đến formula_5 là âm, nó làm tăng khả năng thông qua còn dư từ formula_4 đến formula_5.
Chú ý là chiều dài đường tăng luồng (màu đỏ) không bao giờ giảm. Đường tăng tìm được luôn là ngắn nhất có thể. Luồng tìm được bằng tổng khả năng thông qua của lát cắt cực tiểu trong đồ thị chia cắt đỉnh phát và đỉnh thu. Có đúng một lát cắt nhỏ nhất trong đồ thị này, chia tập hợp đỉnh thành formula_11 và formula_12, và có khả năng thông qua