Thuật_toán_Ford-Fulkerson

Thuật toán Ford- Fulkerson (đặt theo L. R. FordD. R. Fulkerson) tính toán luồng cực đại trong một mạng vận tải. Tên Ford-Fulkerson cũng thường được sử dụng cho thuật toán Edmonds-Karp, một trường hợp đặc biệt của thuật toán Ford-Fulkerson.Ý tưởng đằng sau thuật toán rất đơn giản: miễn là tồn tại một đường đi từ nguồn (nút bắt đầu) đến điểm xả (nút cuối), với điều kiện tất cả các cung trên đường đi đó vẫn còn khả năng thông qua, thì ta sẽ gửi đi một luồng dọc theo đường đi đó. Sau đó chúng ta tìm một đường đi khác, và tiếp tục như vậy. Một đường đi còn khả năng thông qua là một đường đi có khả năng mở rộng thêm hay một đường đi mà luồng qua đó còn khả năng tăng thêm - gọi tắt là đường tăng.