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_BULLET 1 Khởi tạo formula _ 34 với mọi formula _ 35 BULLET 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 BULLET 3 Tìm luồng ngăn_chặn formula _ 23 trong formula _ 26 BULLET 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 tuỳ_ý 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 BULLET Thuật_toán Ford Fulkerson_BULLET_Bài toán luồng cực_đại
Thuật_toán Dinitz