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.^[1] Thuật toán chạy trong thời gian ${\displaystyle O(V^{2}E)}$ và tương tự như thuật toán Edmonds–Karp, chạy trong thời gian ${\displaystyle O(VE^{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ử ${\displaystyle G=((V,E),c,s,t)}$ là một mạng lưới với khả năng thông qua ${\displaystyle c(u,v)}$ và luồng ${\displaystyle f(u,v)}$ trên cung ${\displaystyle (u,v)}$.

Khả năng thông qua còn dư là một ánh xạ ${\displaystyle c_{f}:V\times V\to R^{+}}$ định nghĩa như sau,

1. nếu ${\displaystyle (u,v)\in E}$, thì

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

   ${\displaystyle c_{f}(v,u)=f(u,v)}$

2. ${\displaystyle c_{f}(u,v)=0}$ nếu không phải.

Đồ thị còn dư là đồ thị ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$, trong đó

${\displaystyle E_{f}=\{(u,v)\in V\times V:c_{f}(u,v)>0\}}$.

Một đường tăng luồng là một đường ${\displaystyle s-t}$ trên đồ thị còn dư ${\displaystyle G_{f}}$.

Định nghĩa ${\displaystyle \operatorname {dist} (v)}$ là độ dài đường đi ngắn nhất (tính theo số cung) từ ${\displaystyle s}$ đến ${\displaystyle v}$ trên ${\displaystyle G_{f}}$. Đồ thị tầng của ${\displaystyle G_{f}}$ là đồ thị ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$, trong đó

${\displaystyle E_{L}=\{(u,v)\in E_{f}:\operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

Một luồng ngăn chặn là một luồng ${\displaystyle f'}$ từ ${\displaystyle s}$ đến ${\displaystyle t}$ trên đồ thị ${\displaystyle G_{L}}$ sao cho đồ thị ${\displaystyle G'=(V,E_{L}',s,t)}$ với ${\displaystyle E_{L}'=\{(u,v):f'(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ không có đường ${\displaystyle s-t}$ nào.

Thuật toán

Thuật toán Dinitz

Dữ liệu vào: Mạng ${\displaystyle G=((V,E),c,s,t)}$.

Dữ liệu ra: Một luồng ${\displaystyle f}$ từ ${\displaystyle s}$ đến ${\displaystyle t}$ có giá trị lớn nhất.

1. Khởi tạo ${\displaystyle f(e)=0}$ với mọi ${\displaystyle e\in E}$.
2. Xây dựng ${\displaystyle G_{L}}$ từ ${\displaystyle G_{f}}$ của ${\displaystyle G}$. Nếu ${\displaystyle \operatorname {dist} (t)=\infty }$, thì dừng và đưa ra kết quả ${\displaystyle f}$.
3. Tìm luồng ngăn chặn ${\displaystyle f'}$ trong ${\displaystyle G_{L}}$.
4. Tăng luồng ${\displaystyle \ f}$ bằng cách thêm ${\displaystyle f'}$ 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á ${\displaystyle n-1}$ luồng ngăn chặn, trong đó ${\displaystyle n}$ là số đỉnh của đồ thị. Có thể xây dựng đồ thị tầng ${\displaystyle G_{L}}$ bằng tìm kiếm theo chiều rộng trong thời gian ${\displaystyle O(E)}$ và có thể tìm luồng ngăn chặn trong thời gian ${\displaystyle O(VE)}$. Do đó thời gian chạy của thuật toán Dinitz là ${\displaystyle O(V^{2}E)}$.

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 ${\displaystyle O(E\log V)}$ và do đó giảm thời gian chạy của thuật toán Dinitz xuống ${\displaystyle O(VE\log V)}$.

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 ${\displaystyle O(E)}$, 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 ${\displaystyle O({\sqrt {E}})}$ và ${\displaystyle O(V^{2/3})}$. Do đó thuật toán chạy trong thời gian ${\displaystyle O(\min(V^{2/3},E^{1/2})E)}$.

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à ${\displaystyle O({\sqrt {V}})}$, nên thời gian chạy là không quá ${\displaystyle O({\sqrt {V}}E)}$. 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 ý.^[2]

Ví dụ

Dưới đây là một ví dụ thực hiện thuật toán Dinitz. Trong đồ thị tầng ${\displaystyle G_{L}}$, nhãn đỏ của các đỉnh là các giá trị ${\displaystyle \operatorname {dist} (v)}$. Các đường màu xanh tạo thành một luồng ngăn chặn.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	Luồng ngăn chặn bao gồm ${\displaystyle \{s,1,3,t\}}$ với 4 đơn vị luồng, ${\displaystyle \{s,1,4,t\}}$ với 6 đơn vị luồng, và ${\displaystyle \{s,2,4,t\}}$ với 4 đơn vị luồng. Do đó luồng ngăn chặn có 14 đơn vị luồng và tổng giá trị luồng ${\displaystyle |f|}$ là 14. Ghi chú là mỗi đường tăng luồng có 3 cung.
2.
	Luồng ngăn chặn bao gồm ${\displaystyle \{s,2,4,3,t\}}$ với 5 đơn vị luồng. Do đó luồng ngăn chặn có 5 đơn vị luồng và tổng giá trị luồng ${\displaystyle |f|}$ là 14 + 5 = 19. Ghi chú là mỗi đường tăng luồng có 4 cung.
3.
	Vì không thể đến được ${\displaystyle t}$ trong đồ thị ${\displaystyle G_{f}}$, thuật toán kết thúc và trả về kết quả 19. Ghi chú là trong mỗi luồng ngăn chặn, số cung của mỗi đường tăng luồng tăng lên ít nhất một 1.

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

Ghi chú

1. Yefim Dinitz (1970). “Algorithm for solution of a problem of maximum flow in a network with power estimation” (PDF). Doklady Akademii nauk SSSR. 11: 1277–1280.
2. Tarjan 1983, tr. 102.

Tham khảo

• Yefim Dinitz (2006). “Dinitz' Algorithm: The Original Version and Even's Version”. Trong Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman (biên tập). Theoretical Computer Science: Essays in Memory of [[Shimon Even]] (PDF). Springer. tr. 218–240. ISBN 978-3-540-32880-3. Bản gốc (PDF) lưu trữ ngày 20 tháng 8 năm 2016. Truy cập ngày 14 tháng 9 năm 2012. Tựa đề URL chứa liên kết wiki (trợ giúp)
• Tarjan, R. E. (1983). Data structures and network algorithms.
• B. H. Korte, Jens Vygen (2008). “8.4 Blocking Flows and Fujishige's Algorithm”. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. tr. 174–176. ISBN 978-3-540-71844-4.