Thuật toán Edmonds–Karp

Trong khoa học máy tính và lý thuyết đồ thị, thuật toán Edmonds–Karp là một trường hợp đặc biệt của thuật toán Ford–Fulkerson cho việc tìm luồng cực đại trong mạng. Nó có độ phức tạp tính toán O(V E²). Độ phức tạp tính toán của nó cao hơn của thuật toán gán lại nhãn-lên đầu (O(V³)), nhưng nó thường chạy nhanh hơn trên đồ thị thưa. Thuật toán này được xuất bản lần đầu tiên bởi Yefim (Chaim) Dinic năm 1970^[1] và một cách độc lập bởi Jack Edmonds và Richard Karp năm 1972^[2]. Thuật toán Dinic có thêm một số cải tiến giúp giảm thời gian chạy xuống O(V²E).

Thuật toán[sửa | sửa mã nguồn]

Cấu trúc của thuật toán giống hệt như thuật toán Ford–Fulkerson, chỉ khác cách lựa chọn đường tăng luồng. Đường tăng luồng được chọn là đường tăng có ít cung nhất. Có thể tìm đường tăng này bằng tìm kiếm theo chiều rộng. Có thể chứng minh thời gian chạy của thuật toán là O(VE²) như sau. Thời gian để tìm mỗi đường tăng là O(E). Sau mỗi lần tăng luồng, ít nhất một cung của đồ thị trở thành bão hòa. Mỗi lần một cung trong E trở nên bão hòa (một cung có thể trở thành bão hòa nhiều lần), khoảng cách từ nguồn tới cung bị bão hòa tăng lên ít nhất 1 so với lần cuối cùng nó bị bão hòa trước đó. Khoảng cách này không bao giờ vượt quá V. Một tính chất nữa là khoảng cách từ nguồn tới một đỉnh bất kì là không giảm trong suốt quá trình tăng luồng. Có thể tham khảo một chứng minh đơn giản cho tính chất này ở Cormen và đồng nghiệp (2001). Như vậy số lần tăng luồng là không quá O(VE) và thời gian chạy là O(VE²).

Mã giả[sửa | sửa mã nguồn]

Xem mô tả chi tiết hơn tại Thuật toán Ford-Fulkerson

Ví dụ[sửa | sửa mã nguồn]

Xét một mạng gồm bảy đỉnh, đỉnh phát A, đỉnh thu G, và khả năng thông qua được cho trong hình dưới đây:

Trong cặp số $f/c$ trên mỗi cung, $f$ là luồng hiện tại, và $c$ khả năng thông qua. Khả năng thông qua còn dư từ $u$ đến $v$ là $c_{f}(u,v)=c(u,v)-f(u,v)$ , hiệu của khả năng thông qua và luồng hiện tại. Nếu luồng từ $u$ đến $v$ là âm, nó làm tăng khả năng thông qua còn dư từ $u$ đến $v$ .

Khả năng thông qua	Đường
Khả năng thông qua	Mạng thu được
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0,2-0,1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-0,4-0,1-0,6-2,9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,4-1,2-0,0--1,6-3,9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

Chú ý là chiều dài đường tăng luồng (màu đỏ) không bao giờ giảm. Đường tăng tìm được luôn là ngắn nhất có thể. Luồng tìm được bằng tổng khả năng thông qua của lát cắt cực tiểu trong đồ thị chia cắt đỉnh phát và đỉnh thu. Có đúng một lát cắt nhỏ nhất trong đồ thị này, chia tập hợp đỉnh thành $\{A,B,C,E\}$ và $\{D,F,G\}$ , và có khả năng thông qua

c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\

Ghi chú[sửa | sửa mã nguồn]

^ Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady. Doklady. 11: 1277–1280.
^ Edmonds, Jack; Karp, Richard M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM. Association for Computing Machinery. 19 (2): 248–264. doi:10.1145/321694.321699.

Tham khảo[sửa | sửa mã nguồn]

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “26.2”, Introduction to Algorithms (ấn bản 2), MIT Press and McGraw–Hill, tr. 660–663, ISBN 0-262-53196-8
Algorithms and Complexity (xem trang 63–69). http://www.cis.upenn.edu/~wilf/AlgComp3.html Lưu trữ 2006-10-05 tại Wayback Machine

[1] Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady. Doklady. 11: 1277–1280.

[2] Edmonds, Jack; Karp, Richard M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM. Association for Computing Machinery. 19 (2): 248–264. doi:10.1145/321694.321699.

[1]

[2]