Thuật toán Ford–Fulkerson

Thuật toán Ford- Fulkerson (đặt theo L. R. Ford và D. 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".

==Thuật toán==
Cho một đồ thị formula_1, với các khả năng thông qua formula_2 và luồng formula_3 trên các cung từ formula_4 đến formula_5, ta muốn tìm luồng cực đại từ đầu nguồn formula_6 đến điểm thoát formula_7. Sau mỗi bước, các điều kiện sau đây được duy trì:

- formula_8. Luồng từ formula_4 tới formula_5 không vượt quá khả năng thông qua.
- formula_11. Ta duy trì cân bằng luồng.
- formula_12 cho tất cả các nút ngoại trừ formula_6 và formula_7. Lượng dòng chảy vào một nút bằng lượng chảy ra khỏi một nút.

Điều này có nghĩa là một luồng đi qua một mạng là một luồng "hợp lệ" sau mỗi vòng của thuật toán. Chúng ta định nghĩa mạng còn dư formula_15 là mạng với sức chứa formula_16 và luồng bằng không. Chú ý rằng không chắc chắn là formula_17, bởi vì việc gửi luồng theo cung formula_18 có thể làm ngắt formula_18 (làm nó bão hòa), nhưng lại mở một cung mới formula_20 trong mạng còn dư.

Có thể tìm đường đi trong formula_15 bằng các phương pháp chẳng hạn như tìm kiếm theo chiều rộng ("breadth-first-search") hoặc tìm kiếm theo chiều sâu ("depth-first-search"). Nếu sử dụng cách thứ nhất, thuật toán sẽ được gọi là Edmonds-Karp.

==Độ phức tạp==
Bằng cách thêm luồng trên đường tăng vào luồng đã được thiết lập trên đồ thị, ta sẽ đạt đến luồng cực đại khi trên đồ thị không còn tìm được thêm đường tăng luồng nào nữa. Tuy nhiên, không chắc chắn là tình huống này sẽ đạt được, do vậy điều tốt nhất có thể được đảm bảo là: nếu thuật toán kết thúc thì kết quả sẽ là lời giải đúng. Trong trường hợp thuật toán chạy vô hạn, luồng có thể không hội tụ về phía luồng cực đại. 
Tuy nhiên, tình huống này chỉ xảy ra với luồng có giá trị vô tỷ. Khi khả năng thông qua là các số tự nhiên, thời gian chạy của thuật toán Ford-Fulkerson bị chặn bởi O("E*f"), trong đó "E" là số cung của đồ thị và "f" là luồng cực đại trên đồ thị. Điều này là bởi vì mỗi đường tăng được tìm ra trong thời gian O("E") và nó làm tăng luồng với một lượng có giá trị nguyên không nhỏ hơn 1.

Một biến thể của thuật toán Ford-Fulkerson bảo đảm sự kết thúc và thời gian chạy không phụ thuộc vào giá trị luồng cực đại là thuật toán Edmonds-Karp, chạy trong thời gian O("VE").

==Ví dụ==
Ví dụ sau đây cho thấy những bước ban đầu của thuật toán Ford-Fulkerson trong một mạng vận tải gồm 4 nút, nguồn "A" và thoát "D". Các đường đi tăng được tìm bằng phương pháp tìm kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo thứ tự bảng chữ cái. Ví dụ này cho thấy biểu hiện của trường hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một luồng giá trị 1 qua mạng. Nếu sử dụng phép tìm theo chiều rộng thay vì theo chiều sâu, ta sẽ chỉ cần hai bước.

Chú ý khi luồng bị "đẩy ngược" từ "C" đến "B" khi tìm được đường đi "A,C,B,D".

==Tham khảo==
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.2: The Ford-Fulkerson method, pp. 651–664.

==Liên kết ngoài==
- Bài toán luồng cực đại trên mạng - Các thuật toán đa thức
- Animation of Ford-Fulkerson algorithm