Giáo trình Đồ thị và các thuật toán - Chương 7: Mạng vận tải

7.2.1 Thuật toán gán nhãn để tìm luồng lớn nhất A. Quá trình gán nhãn Mỗi đình chỉ có thể có một trong ba khả năng: 1, được gán nhân và được kiểm tra (tức là nó được gán nhãn và tất cả các đinh liên thuộc với nó đã được xử lý); hoặc 2. được gán nhãn và chưa được kiểm tra (tức là nó được gán nhãn và tồn tại đỉnh liên thuộc với nó chưa được xử lý); hoặc 3. chưa được gán nhãn. Nhãn của đỉnh vi gồm hai thành phần và có một trong hai dạng hoặc (+), 8) hoặc (-3, 6). Trong trường hợp đầu, có thể tăng luồng dọc theo cung (vi, tỷ); trong trường hợp thứ hai, có thể giảm luồng dọc theo cung (ti, vị). Đại lượng ở trong cả hai trường hợp là lượng hàng nhiều nhất có thể thêm hoặc bớt giá trị của luồng trên các công thuộc dây chuyền điều chinh (trong quá trình xây dựng) từ 8 đến tị. Nhãn của đỉnh ti cho phép xác định dây chuyền điều chỉnh luồng từ s đến dị. Khởi tạo tất cả các đỉnh chưa được gán nhãn và fij = 0 với mọi cung (ti, vị) € E.