Thuật toán Dinitz

Thuật toán Dinitz là một thuật toán thời gian đa thức mạnh cho việc tìm luồng cực đại trên đồ thị luồng, tìm ra năm 1970 bởi nhà nghiên cứu khoa học máy tính người Israel (trước đó ở Liên Xô) Yefim Dinitz. Thuật toán chạy trong thời gian formula_1 và tương tự như thuật toán Edmonds–Karp, chạy trong thời gian formula_2, ở chỗ nó cũng dùng đường tăng luồng ngắn nhất (ít cung nhất). Việc sử dụng các khái niệm "đồ thị tầng" và "luồng ngăn chặn" cho phép thuật toán Dinitz đạt được thời gian nhanh hơn.

==Định nghĩa==
Giả sử formula_3 là một mạng lưới với khả năng thông qua formula_4 và luồng formula_5 trên cung formula_6.

==Thuật toán==
Thuật toán Dinitz
1. Khởi tạo formula_34 với mọi formula_35.
2. Xây dựng formula_26 từ formula_15 của formula_38. Nếu formula_39, thì dừng và đưa ra kết quả formula_31.
3. Tìm luồng ngăn chặn formula_23 trong formula_26.
4. Tăng luồng formula_43 bằng cách thêm formula_23 và quay lại bước 2.

==Phân tích==
Có thể chứng minh rằng khoảng cách (tính theo số cung) từ đỉnh phát đến đỉnh thu tăng lên ít nhất 1 sau mỗi lần tăng luồng bằng luồng ngăn chặn nên chỉ cần tìm không quá formula_45 luồng ngăn chặn, trong đó formula_46 là số đỉnh của đồ thị. Có thể xây dựng đồ thị tầng formula_26 bằng tìm kiếm theo chiều rộng trong thời gian formula_48 và có thể tìm luồng ngăn chặn trong thời gian formula_49. Do đó thời gian chạy của thuật toán Dinitz là formula_1.

Bằng cách sử dụng cấu trúc dữ liệu cây động, có thể giảm thời gian tìm mỗi luồng ngăn chặn xuống còn formula_51 và do đó giảm thời gian chạy của thuật toán Dinitz xuống formula_52.

=== Trường hợp đặc biệt ===
Trong mạng với khả năng thông qua đơn vị, thời gian chạy của thuật toán nhanh hơn rất nhiều so với trường hợp tổng quát. Có thể tìm mỗi luồng ngăn chặn trong thời gian formula_48, và có thể chứng minh rằng số lần tìm luồng ngăn chặn là không quá số nhỏ hơn giữa formula_54 và formula_55. Do đó thuật toán chạy trong thời gian formula_56.

Trong mạng lưới xây dựng từ bài toán ghép cặp trên đồ thị hai phía, số lần tìm luồng ngăn chặn là formula_57, nên thời gian chạy là không quá formula_58. Thuật toán này còn được biết đến là thuật toán Hopcroft–Karp. Tổng quát hơn, chặn trên cho thời gian chạy này đúng cho mọi "mạng đơn vị" — mạng trong đó mỗi đỉnh, ngoại trừ đỉnh phát và đỉnh thu, hoặc có đúng một cung vào với khả năng thông qua bằng một, hoặc đúng một cung ra với khả năng thông qua bằng một và tất cả các cung khác có khả năng thông qua là số nguyên tùy ý.

==Ví dụ==
Dưới đây là một ví dụ thực hiện thuật toán Dinitz. Trong đồ thị tầng formula_26, nhãn đỏ của các đỉnh là các giá trị formula_16. Các đường màu xanh tạo thành một luồng ngăn chặn.

==Lịch sử==
Thuật toán Dinitz được xuất bản năm 1970 bởi nhà nghiên cứu khoa học máy tính người Nga (khi đó) Yefim (Chaim) A. Dinitz, nay là thành viên của khoa Khoa học Máy tính tại đại học Ben-Gurion (Israel), trước thuật toán Edmonds–Karp, xuất bản năm 1972 nhưng được phát hiện trước đó. Họ chứng minh một cách độc lập rằng trong thuật toán Ford–Fulkerson, nếu mỗi đường tăng luồng luôn là đường tăng ngắn nhất, chiều dài của đường tăng luồng là không giảm.

==Xem thêm==
- Thuật toán Ford–Fulkerson
- Bài toán luồng cực đại