09.2 - Min Cost Flow với chi phí âm

Giới thiệu

Trong khi cải tiến thuật toán ở phần trước với Dinic, chúng ta sử dụng Dijsktra để tìm đường đi ngắn nhất trên mạng thặng dư GR sau mỗi lần tăng luồng. Do bản chất thuật toán Dijsktra hoạt động bất ổn (có thể ra kết quả sai) khi đồ thị chứa trọng số âm, chúng ta cần thêm một số cải tiến để có thể khắc phục được tình trạng này.

Chủ đề này thảo luận một số vấn đề liên quan đến việc tiền sử lý, kết hợp thêm các thuật toán khác trong việc cải tiến bài toán Min Cost Flow khi mạng luồng chứa cạnh có chi phí thông qua âm.

Tài liệu tham khảo

1. CP-Algorithm - Minimum-Cost Flow

2. CodeForce Tutorial - Minimum Cost Flow

3. Topcoder  - Minimum Cost Flow: Key Concept and Part two

4. Hackerearth - Minimum Cost Flow

5. Steven Halim - Competitive Programming 4 - MinCost Flow - Chapter 9, page 571 - 579

6. Brillian.org - Johnson's Algorithm

7. GeeksforGeeks - Johnson's Algorithm

Một số khái niệm liên quan

Thuật toán JohnSon

Đây là thuật toán cho phép tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị có hướng có trọng số và chấp nhật một số cạnh có trọng số âm (nhưng không có chu trình âm).

Ý tưởng chính của thuật toán là dùng thuật toán Bellman-Ford để tìm đường đi ngắn nhất từ s đến mọi đỉnh rời thực hiện chuyển đổi đồ thị sang dạng mới không có trọng số âm trên cạnh nào. Tiếp theo dùng thuật toán Dijsktra tìm đường đi ngắn nhất trên đồ thị mới này. Cuối cùng kết quả trả về là quy đổi giá trị đường đi ngắn nhất ngược về đồ thị góc ban đầu.

Các bước thực hiện cụ thể như sau:

Bước 1. Thêm một đỉnh q vào đồ thị, connect q với các đỉnh khác của đồ thị với chi phí 0.

Bước 2. Dùng Bellman-Ford tìm đường đi ngắn nhất từ q tới mọi đỉnh v, đặt là h(v). Nếu bước này phát hiện chu trình âm thì dừng thuật toán.

Bước 3. Chuyển đổi đồ thị, với mỗi cạnh e(u, v) trên G có trọng số w(u, v) ta chuyển thành cạnh mới với trọng số w(u,v) + h(u) − h(v) 

Bước 4. Loại bỏ đỉnh q. Chạy Dijsktra V lần trên đồ thị mới để tìm đường đi ngắn nhất giữa mọi cặp đỉnh, ta có giá trị đường đi ngắn nhất giữa mọi định u, v là D(u, v)

Bước 5. Chuyển toàn bộ đường đi ngắn nhất này về giá trị gốc bằng cách D(u, v) += h(v)-h(u)

Nguồn: wikipedia

Mã giả thuật toán trên chi tiết như sau:

Johnson(G)

    1.

    create G` where G`.V = G.V + {s},

        G`.E = G.E + ((s, u) for u in G.V), and 

        weight(s, u) = 0 for u in G.V

    2.

    if Bellman-Ford(s) == False

        return "The input graph has a negative weight cycle"

    else:

        for vertex v in G`.V:

            h(v) = distance(s, v) computed by Bellman-Ford

        for edge (u, v) in G`.E:

            weight`(u, v) = weight(u, v) + h(u) - h(v)

    3.

        D = new matrix of distances initialized to infinity

        for vertex u in G.V:

            run Dijkstra(G, weight`, u) to compute distance`(u, v) for all v in G.V

            for each vertex v in G.V:

                D_(u, v) = distance`(u, v) + h(v) - h(u)

        return D

Nguồn: https://brilliant.org/

Thế năng - Potential

Cách chuyển đổi trên được nhiều tài liệu gọi tên Potential (tạm dịch là thế năng), với ý nghĩa rằng chi phí trên đường đi được cộng thêm một lượng thay đổi (chênh lệch) ở điểm cuối của nó.

Ý tưởng về Potential (thế năng) này sẽ được áp dụng vào bài toán Min Cost Flow cho việc tìm đường đi ngắn nhất dựa vào chi phí thông luồng.

Toàn bộ ý tưởng, mã giả, giải thuật và sourcode của thuật toán Johnson có thể tham khảo tại: Brilliant.org, Wikipedia, GeeksforGeeks

Cải tiến thuật toán Min Cost Flow cho mạng có chi phí âm

Bây giờ chúng ta đã có thể hiểu được cách cải tiến cho bài toán Min Cost Flow khi trong mạng có chi phí âm. Thuật toán có thể tóm tắt như sau:

Cài đặt chi tiết tham khảo

Nhiệm vụ 2 - Nâng cao

Nhiệm vụ 2.1. Codeforce - Four Melodies

Nhiệm vụ 2.2. Codeforce - April Fools' Problem 

Nhiệm vụ 2.3. Codeforce - Team Building

Nhiệm vụ 2.4. Codeforce - Cow and Exercise

Nhiệm vụ 2.5. Thực hiện contest ngắn - Min Cost Flow 2 (Tuần sau làm)