Khóa học CTDL và GT

Bài 22.3: Thuật toán Bellman-Ford và phát hiện chu trình âm

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật!

Trong các bài trước, chúng ta đã khám phá thuật toán Dijkstra - một công cụ tuyệt vời để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số cạnh không âm. Nhưng cuộc sống không phải lúc nào cũng "không âm", và trong thế giới đồ thị, chúng ta hoàn toàn có thể gặp phải những cạnh có trọng số âm. Vậy điều gì xảy ra khi có cạnh âm? Và làm thế nào để tìm đường đi ngắn nhất trong trường hợp đó?

Đây chính là lúc Thuật toán Bellman-Ford tỏa sáng! Bellman-Ford không chỉ giải quyết được bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số âm, mà còn có một khả năng cực kỳ quan trọng khác: phát hiện chu trình âm (negative cycle).

Tại sao Dijkstra không đủ?

Nhớ lại cách hoạt động của Dijkstra: nó dựa trên ý tưởng "tham lam", luôn chọn đỉnh có khoảng cách tạm thời nhỏ nhất để mở rộng. Nó giả định rằng khi một đỉnh được "chốt" (thêm vào tập các đỉnh đã tìm thấy đường đi ngắn nhất), thì khoảng cách đến nó là cuối cùng và không thể được cải thiện thêm nữa. Điều này đúng với trọng số không âm, bởi vì việc đi thêm qua bất kỳ cạnh nào chỉ có thể làm tăng hoặc giữ nguyên tổng trọng số đường đi.

Tuy nhiên, với cạnh có trọng số âm, giả định này bị phá vỡ hoàn toàn. Một đường đi tưởng chừng đã dài hơn lại có thể trở thành đường đi ngắn nhất nếu nó đi qua một cạnh âm có trọng số đủ nhỏ. Ví dụ, đường đi từ A đến C trực tiếp là 5, nhưng đường đi A -> B -> C với trọng số A->B là 3 và B->C là -4 có tổng là 3 + (-4) = -1, rõ ràng ngắn hơn! Dijkstra sẽ gặp khó khăn trong việc xử lý các kịch bản như thế này một cách chính xác.

Giới thiệu về Thuật toán Bellman-Ford

Bellman-Ford là một thuật toán dựa trên kỹ thuật nới lỏng cạnh (edge relaxation). Ý tưởng cốt lõi là: chúng ta sẽ lặp đi lặp lại việc đi qua tất cả các cạnh trong đồ thị và thử "nới lỏng" chúng. Nới lỏng một cạnh (u, v) với trọng số w nghĩa là kiểm tra xem liệu đi từ đỉnh nguồn đến u, rồi từ u đến v, có tạo ra một đường đi ngắn hơn đến v so với khoảng cách hiện tại đã biết đến v hay không.

Nếu dist[u] + w < dist[v], thì chúng ta đã tìm thấy một đường đi ngắn hơn đến v thông qua u. Chúng ta cập nhật dist[v] = dist[u] + w. Quá trình này được gọi là relaxation.

Điểm mấu chốt của Bellman-Ford là nó thực hiện quá trình nới lỏng này một số lần cụ thể.

Các bước của Thuật toán Bellman-Ford

Bellman-Ford hoạt động theo các bước sau:

1. Khởi tạo:

   • Tạo một mảng dist có kích thước V (số đỉnh), lưu trữ khoảng cách ngắn nhất từ đỉnh nguồn đến mỗi đỉnh khác. Khởi tạo dist[source] = 0 và dist[v] = INF (với INF là một giá trị vô cực đủ lớn) cho tất cả các đỉnh v != source.
   • (Tùy chọn) Một mảng parent để lưu trữ đỉnh trước đó trên đường đi ngắn nhất, cho phép tái tạo lại đường đi sau này.

2. Lặp lại Nới lỏng (V-1 lần):

   • Lặp lại quá trình sau V - 1 lần:
     • Duyệt qua tất cả các cạnh (u, v) trong đồ thị với trọng số w.
     • Nếu dist[u] != INF và dist[u] + w < dist[v]:
       • Cập nhật dist[v] = dist[u] + w.
       • (Tùy chọn) Cập nhật parent[v] = u.

3. Kiểm tra Chu trình âm:

   • Sau khi hoàn thành V-1 lần lặp nới lỏng, thực hiện thêm một lần duyệt qua tất cả các cạnh (u, v) với trọng số w.
   • Nếu tìm thấy bất kỳ cạnh nào mà dist[u] != INF và dist[u] + w < dist[v]:
     • Điều này chứng tỏ tồn tại một chu trình âm (negative cycle) có thể đạt được từ đỉnh nguồn. Trong trường hợp có chu trình âm, đường đi ngắn nhất đến các đỉnh trong chu trình (hoặc có thể đạt được từ chu trình) sẽ không xác định (có thể tiến về -vô cực). Bellman-Ford sẽ báo cáo rằng tồn tại chu trình âm.
   • Nếu không có cạnh nào thỏa mãn điều kiện trên sau lần duyệt thứ V, thì không có chu trình âm nào reachable từ nguồn, và mảng dist chứa khoảng cách ngắn nhất từ nguồn đến tất cả các đỉnh khác.

Tại sao lại lặp lại V-1 lần?

Trong một đồ thị có V đỉnh và không chứa chu trình âm, đường đi ngắn nhất từ đỉnh nguồn đến bất kỳ đỉnh nào khác là một đường đi đơn giản (simple path - không lặp lại đỉnh). Đường đi đơn giản dài nhất trong một đồ thị có V đỉnh chỉ có thể chứa tối đa V đỉnh, và do đó, có tối đa V-1 cạnh.

Mỗi lần lặp qua tất cả các cạnh (sau lần lặp đầu tiên), thuật toán đảm bảo rằng nếu có một đường đi ngắn nhất đến đỉnh v với k cạnh, thì khoảng cách đến v sẽ được cập nhật đúng sau lần lặp thứ k. Do đường đi ngắn nhất dài nhất có V-1 cạnh, sau V-1 lần lặp, khoảng cách đến tất cả các đỉnh có đường đi ngắn nhất từ nguồn (mà không đi qua chu trình âm) sẽ được xác định chính xác.

Tại sao kiểm tra chu trình âm sau V-1 lần?

Nếu sau V-1 lần lặp, chúng ta vẫn có thể nới lỏng một cạnh (tức là dist[u] + w < dist[v]), điều đó chỉ có thể xảy ra nếu có một chu trình âm. Tại sao? Bởi vì nếu không có chu trình âm, tất cả các khoảng cách đã đạt đến giá trị ngắn nhất của chúng sau V-1 lần lặp. Nếu khoảng cách vẫn tiếp tục giảm, nghĩa là chúng ta đang đi vào một vòng lặp các cạnh có tổng trọng số âm, cho phép khoảng cách giảm mãi mãi.

Ví dụ Minh Họa (Không có Chu trình Âm)

Xét đồ thị sau với 5 đỉnh (0, 1, 2, 3, 4) và các cạnh có trọng số, bao gồm cả trọng số âm. Đỉnh nguồn là 0.

Cạnh: (0, 1, -1) (0, 2, 4) (1, 2, 3) (1, 3, 2) (1, 4, 2) (3, 2, 5) (3, 1, 1) (4, 3, -3)

Bước 1: Khởi tạo

dist array: [0, INF, INF, INF, INF] (Giả sử INF là một số rất lớn)

Bước 2: Lặp V-1 = 4 lần nới lỏng

• Lần lặp 1:

  • (0, 1, -1): dist[0] + (-1) = 0 - 1 = -1 < dist[1](INF). Update dist[1] = -1. dist = [0, -1, INF, INF, INF]
  • (0, 2, 4): dist[0] + 4 = 0 + 4 = 4 < dist[2](INF). Update dist[2] = 4. dist = [0, -1, 4, INF, INF]
  • Các cạnh khác (1, x), (3, x), (4, x): dist[u] là INF hoặc việc nới lỏng không cải thiện.
  • Kết thúc lần 1: dist = [0, -1, 4, INF, INF]

• Lần lặp 2:

  • (0, 1, -1): -1 vẫn là giá trị nhỏ nhất cho dist[1].
  • (0, 2, 4): 4 vẫn là giá trị nhỏ nhất cho dist[2].
  • (1, 2, 3): dist[1] + 3 = -1 + 3 = 2 < dist[2](4). Update dist[2] = 2. dist = [0, -1, 2, INF, INF]
  • (1, 3, 2): dist[1] + 2 = -1 + 2 = 1 < dist[3](INF). Update dist[3] = 1. dist = [0, -1, 2, 1, INF]
  • (1, 4, 2): dist[1] + 2 = -1 + 2 = 1 < dist[4](INF). Update dist[4] = 1. dist = [0, -1, 2, 1, 1]
  • (3, 2, 5): dist[3] + 5 = 1 + 5 = 6 > dist[2](2). Không update.
  • (3, 1, 1): dist[3] + 1 = 1 + 1 = 2 > dist[1](-1). Không update.
  • (4, 3, -3): dist[4] + (-3) = 1 - 3 = -2 < dist[3](1). Update dist[3] = -2. dist = [0, -1, 2, -2, 1]
  • Kết thúc lần 2: dist = [0, -1, 2, -2, 1]

• Lần lặp 3:

  • (0, 1, -1): -1 không thay đổi.
  • (0, 2, 4): 4 > dist[2](2). Không thay đổi.
  • (1, 2, 3): dist[1] + 3 = -1 + 3 = 2. dist[2] vẫn là 2.
  • (1, 3, 2): dist[1] + 2 = -1 + 2 = 1 > dist[3](-2). Không thay đổi.
  • (1, 4, 2): dist[1] + 2 = -1 + 2 = 1. dist[4] vẫn là 1.
  • (3, 2, 5): dist[3] + 5 = -2 + 5 = 3 > dist[2](2). Không thay đổi.
  • (3, 1, 1): dist[3] + 1 = -2 + 1 = -1. dist[1] vẫn là -1.
  • (4, 3, -3): dist[4] + (-3) = 1 - 3 = -2. dist[3] vẫn là -2.
  • Lưu ý: Trong lần lặp này, chúng ta xem xét lại các cạnh, có thể có những đường đi ngắn hơn được tìm thấy nhờ các cập nhật ở lần lặp trước.
  • Ví dụ: Sau lần lặp 2, dist[3] được cập nhật thành -2 (thông qua 0 -> 1 -> 4 -> 3). Bây giờ, khi nới lỏng cạnh (3, 2, 5): dist[3] + 5 = -2 + 5 = 3. dist[2] hiện tại là 2. Không có cập nhật.
  • Kết thúc lần 3: dist = [0, -1, 2, -2, 1]. Không có cập nhật nào xảy ra trong lần lặp 3.

• Lần lặp 4:

  • Duyệt qua tất cả các cạnh một lần nữa.
  • Không có cập nhật nào xảy ra.
  • Kết thúc lần 4: dist = [0, -1, 2, -2, 1].

Bước 3: Kiểm tra Chu trình âm

Duyệt qua tất cả các cạnh lần thứ 5 (lần thứ V). Kiểm tra xem có cạnh (u, v) với trọng số w nào mà dist[u] != INF và dist[u] + w < dist[v] không. Sau 4 lần lặp, mảng dist đã ổn định: [0, -1, 2, -2, 1]. Duyệt các cạnh:

• (0, 1, -1): dist[0] + (-1) = 0 - 1 = -1. -1 == dist[1]. OK.
• (0, 2, 4): dist[0] + 4 = 0 + 4 = 4. 4 > dist[2](2). OK.
• (1, 2, 3): dist[1] + 3 = -1 + 3 = 2. 2 == dist[2]. OK.
• (1, 3, 2): dist[1] + 2 = -1 + 2 = 1. 1 > dist[3](-2). OK.
• (1, 4, 2): dist[1] + 2 = -1 + 2 = 1. 1 == dist[4]. OK.
• (3, 2, 5): dist[3] + 5 = -2 + 5 = 3. 3 > dist[2](2). OK.
• (3, 1, 1): dist[3] + 1 = -2 + 1 = -1. -1 == dist[1]. OK.
• (4, 3, -3): dist[4] + (-3) = 1 - 3 = -2. -2 == dist[3]. OK.

Không có cạnh nào thỏa mãn điều kiện nới lỏng trong lần kiểm tra này. Do đó, không có chu trình âm reachable từ nguồn. Mảng dist chứa khoảng cách ngắn nhất: Đỉnh 0: 0 Đỉnh 1: -1 Đỉnh 2: 2 Đỉnh 3: -2 Đỉnh 4: 1

Đường đi ngắn nhất đến đỉnh 3 là 0 -> 1 -> 4 -> 3 (0 + (-1) + 2 + (-3) = -2).

C++ Code cho Ví dụ 1 (Không Chu trình Âm)

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits

const int INF = std::numeric_limits<int>::max(); // Sử dụng giá trị vô cực lớn nhất cho int

struct Edge {
    int source, destination, weight;
};

// Hàm thực hiện thuật toán Bellman-Ford
// Trả về true nếu không có chu trình âm reachable từ nguồn, false nếu ngược lại.
bool bellmanFord(int numVertices, const std::vector<Edge>& edges, int source, std::vector<int>& dist) {
    // Bước 1: Khởi tạo
    dist.assign(numVertices, INF);
    dist[source] = 0;

    // Bước 2: Lặp lại nới lỏng V-1 lần
    // numVertices lần lặp, mỗi lần duyệt qua tất cả các cạnh
    for (int i = 0; i < numVertices - 1; ++i) {
        // Biến cờ để kiểm tra xem có bất kỳ cập nhật nào xảy ra trong lần lặp này không
        // Nếu không có cập nhật, khoảng cách đã ổn định, có thể thoát sớm (tối ưu nhỏ)
        // bool updated = false; // Tối ưu nhỏ, bỏ qua để làm rõ logic chính của Bellman-Ford

        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            // Kiểm tra dist[u] != INF để tránh tràn số khi cộng với trọng số âm lớn
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                // updated = true; // Tối ưu nhỏ
            }
        }
        // if (!updated && i > 0) break; // Tối ưu nhỏ: nếu không có cập nhật, thoát sớm
    }

    // Bước 3: Kiểm tra chu trình âm
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (dist[u] != INF && dist[u] + w < dist[v]) {
            // Vẫn có thể nới lỏng => Có chu trình âm reachable từ nguồn
            return false;
        }
    }

    // Không tìm thấy chu trình âm
    return true;
}

int main() {
    int numVertices = 5;
    std::vector<Edge> edges = {
        {0, 1, -1}, {0, 2, 4},
        {1, 2, 3}, {1, 3, 2}, {1, 4, 2},
        {3, 2, 5}, {3, 1, 1},
        {4, 3, -3}
    };
    int source = 0;

    std::vector<int> dist;

    std::cout << "--- Bellman-Ford tren do thi KHONG co chu trinh am ---" << std::endl;

    if (bellmanFord(numVertices, edges, source, dist)) {
        std::cout << "Do thi khong chua chu trinh am reachable tu dinh nguon." << std::endl;
        std::cout << "Khoang cach ngan nhat tu dinh nguon " << source << ":" << std::endl;
        for (int i = 0; i < numVertices; ++i) {
            std::cout << "Den dinh " << i << ": ";
            if (dist[i] == INF) {
                std::cout << "Khong the toi toi";
            } else {
                std::cout << dist[i];
            }
            std::cout << std::endl;
        }
    } else {
        std::cout << "Do thi CHUA chu trinh am reachable tu dinh nguon." << std::endl;
    }

    return 0;
}

Giải thích code:

1. struct Edge: Định nghĩa cấu trúc đơn giản để lưu thông tin về mỗi cạnh: đỉnh nguồn (source), đỉnh đích (destination), và trọng số (weight).
2. const int INF: Sử dụng std::numeric_limits<int>::max() để biểu diễn giá trị vô cực cho khoảng cách ban đầu. Điều này an toàn hơn việc dùng một số cố định lớn như 1e9.
3. bellmanFord function:
   • Nhận vào số đỉnh, danh sách các cạnh, đỉnh nguồn và một tham chiếu đến vector dist để lưu kết quả.
   • Khởi tạo: Gán dist cho tất cả các đỉnh là INF, riêng đỉnh nguồn là 0.
   • Vòng lặp V-1 lần: Vòng lặp for (int i = 0; i < numVertices - 1; ++i) thực hiện quá trình nới lỏng tổng cộng numVertices - 1 lần. Bên trong, nó duyệt qua tất cả các cạnh (for (const auto& edge : edges)) và thực hiện kiểm tra nới lỏng: if (dist[u] != INF && dist[u] + w < dist[v]). Điều kiện dist[u] != INF rất quan trọng để đảm bảo rằng chúng ta chỉ nới lỏng từ các đỉnh mà chúng ta đã biết khoảng cách đến chúng (hoặc là đỉnh nguồn).
   • Kiểm tra Chu trình âm: Sau V-1 lần lặp, một vòng lặp cuối cùng duyệt qua tất cả các cạnh. Nếu bất kỳ cạnh nào vẫn có thể được nới lỏng (dist[u] != INF && dist[u] + w < dist[v]), hàm trả về false để báo hiệu có chu trình âm.
   • Nếu không có chu trình âm nào được phát hiện, hàm trả về true.
4. main function:
   • Định nghĩa số lượng đỉnh và danh sách các cạnh cho ví dụ đồ thị đã phân tích.
   • Gọi hàm bellmanFord với dữ liệu đồ thị.
   • Dựa vào giá trị trả về của bellmanFord, in ra thông báo có chu trình âm hay không.
   • Nếu không có chu trình âm, in ra khoảng cách ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác. Chú ý kiểm tra dist[i] == INF để in thông báo "Khong the toi toi" thay vì giá trị vô cực.

Ví dụ Minh Họa (Có Chu trình Âm)

Bây giờ, xét đồ thị ban đầu và thêm một cạnh tạo thành chu trình âm. Thêm cạnh (1, 0, -4). Chu trình 0 -> 1 -> 0 có tổng trọng số là -1 + (-4) = -5 (âm). Chu trình 1 -> 3 -> 1 có tổng trọng số là 2 + 1 = 3 (dương). Chu trình 1 -> 4 -> 3 -> 1 có tổng trọng số là 2 + (-3) + 1 = 0 (không âm). Chu trình 1 -> 2 -> 3 -> 1 có tổng trọng số là 3 + 5 + 1 = 9 (dương). Chu trình 0 -> 1 -> 0 là chu trình âm và reachable từ đỉnh nguồn 0.

Cạnh: (0, 1, -1) (0, 2, 4) (1, 0, -4) <-- Cạnh mới tạo chu trình âm (1, 2, 3) (1, 3, 2) (1, 4, 2) (3, 2, 5) (3, 1, 1) (4, 3, -3)

Bước 1: Khởi tạo

dist array: [0, INF, INF, INF, INF]

Bước 2: Lặp V-1 = 4 lần nới lỏng

Chúng ta sẽ không đi sâu vào từng bước nhỏ nữa, vì các giá trị sẽ liên tục giảm do chu trình âm. Sau V-1 lần lặp, các giá trị dist có thể đã trở nên rất nhỏ (âm rất sâu), đặc biệt đối với các đỉnh nằm trên hoặc reachable từ chu trình âm. Ví dụ, dist[1] có thể là -1 (qua 0 -> 1), rồi -6 (qua 0 -> 1 -> 0 -> 1), rồi -11, v.v.

Bước 3: Kiểm tra Chu trình âm

Duyệt qua tất cả các cạnh lần thứ 5 (lần thứ V). Xét cạnh (0, 1, -1): dist[0] + (-1) = 0 - 1 = -1. Nếu dist[1] sau 4 lần lặp là -11, thì -1 < -11 là sai. Xét cạnh (1, 0, -4): Giả sử sau 4 lần lặp, dist[1] đã giảm xuống một giá trị âm lớn, ví dụ dist[1] = -11. Khi kiểm tra cạnh (1, 0): dist[1] + (-4) = -11 - 4 = -15. Khoảng cách hiện tại đến đỉnh 0 là dist[0] = 0. Điều kiện nới lỏng dist[u] + w < dist[v] trở thành -15 < 0. Điều này đúng!

Việc tìm thấy một cạnh (1, 0) mà có thể nới lỏng sau V-1 lần lặp chứng tỏ rằng có một chu trình âm (trong trường hợp này là 0 -> 1 -> 0) reachable từ đỉnh nguồn 0. Thuật toán sẽ báo cáo rằng tồn tại chu trình âm.

C++ Code cho Ví dụ 2 (Có Chu trình Âm)

Chúng ta chỉ cần thay đổi danh sách cạnh trong hàm main.

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits

const int INF = std::numeric_limits<int>::max(); // Sử dụng giá trị vô cực lớn nhất cho int

struct Edge {
    int source, destination, weight;
};

// Hàm thực hiện thuật toán Bellman-Ford
// Trả về true nếu không có chu trình âm reachable từ nguồn, false nếu ngược lại.
bool bellmanFord(int numVertices, const std::vector<Edge>& edges, int source, std::vector<int>& dist) {
    dist.assign(numVertices, INF);
    dist[source] = 0;

    for (int i = 0; i < numVertices - 1; ++i) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Bước 3: Kiểm tra chu trình âm
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (dist[u] != INF && dist[u] + w < dist[v]) {
            // Vẫn có thể nới lỏng => Có chu trình âm reachable từ nguồn
            return false;
        }
    }

    // Không tìm thấy chu trình âm
    return true;
}

int main() {
    int numVertices = 5;
    // Thêm cạnh (1, 0, -4) để tạo chu trình âm
    std::vector<Edge> edges = {
        {0, 1, -1}, {0, 2, 4},
        {1, 0, -4}, // <--- Cạnh mới
        {1, 2, 3}, {1, 3, 2}, {1, 4, 2},
        {3, 2, 5}, {3, 1, 1},
        {4, 3, -3}
    };
    int source = 0;

    std::vector<int> dist;

    std::cout << "--- Bellman-Ford tren do thi CO chu trinh am ---" << std::endl;

    if (bellmanFord(numVertices, edges, source, dist)) {
        std::cout << "Do thi khong chua chu trinh am reachable tu dinh nguon." << std::endl;
        std::cout << "Khoang cach ngan nhat tu dinh nguon " << source << ":" << std::endl;
         for (int i = 0; i < numVertices; ++i) {
            std::cout << "Den dinh " << i << ": ";
            if (dist[i] == INF) {
                std::cout << "Khong the toi toi";
            } else {
                std::cout << dist[i];
            }
            std::cout << std::endl;
        }
    } else {
        std::cout << "Do thi CHUA chu trinh am reachable tu dinh nguon!" << std::endl;
        std::cout << "Khong the xac dinh duong di ngan nhat do su ton tai cua chu trinh am." << std::endl;
    }

    return 0;
}

Giải thích code (cho ví dụ có chu trình âm):

Code C++ hoàn toàn giống với ví dụ trước, chỉ khác ở dữ liệu đầu vào edges. Khi chạy với danh sách cạnh mới này, hàm bellmanFord sẽ thực hiện V-1 lần nới lỏng. Do có chu trình âm 0 -> 1 -> 0 với tổng trọng số -5, khoảng cách đến các đỉnh 0 và 1 (và có thể các đỉnh khác reachable từ chu trình này) sẽ tiếp tục giảm sau mỗi lần đi qua chu trình.

Trong vòng kiểm tra chu trình âm cuối cùng, khi thuật toán duyệt qua cạnh (1, 0) với trọng số -4, điều kiện dist[1] + (-4) < dist[0] sẽ đúng (vì dist[1] đã giảm rất sâu sau 4 lần lặp, trong khi dist[0] vẫn là 0). Điều này khiến hàm bellmanFord trả về false, và chương trình chính in ra thông báo về sự tồn tại của chu trình âm.

Phân tích Độ phức tạp

• Độ phức tạp thời gian: Thuật toán Bellman-Ford gồm hai giai đoạn chính:
  • Giai đoạn 1 (V-1 lần nới lỏng): Lặp lại V-1 lần, mỗi lần duyệt qua tất cả E cạnh. Độ phức tạp: O((V-1) E) = O(V E).
  • Giai đoạn 2 (Kiểm tra chu trình âm): Duyệt qua tất cả E cạnh một lần. Độ phức tạp: O(E). Tổng cộng, độ phức tạp thời gian của Bellman-Ford là O(V * E).
• Độ phức tạp không gian: Chúng ta cần lưu trữ danh sách các cạnh (O(E)) và mảng khoảng cách dist (O(V)). Tổng cộng, độ phức tạp không gian là O(V + E).

So với Dijkstra (thường là O(E log V) với Priority Queue), Bellman-Ford chậm hơn đáng kể trên các đồ thị thưa (sparse graphs, E ≈ V) nhưng lại là lựa chọn duy nhất (trong các thuật toán đơn nguồn cơ bản) khi có trọng số âm.

Khi nào sử dụng Bellman-Ford?

• Khi đồ thị có trọng số cạnh âm.
• Khi cần phát hiện chu trình âm.
• Khi đồ thị có ít cạnh (E nhỏ) so với số đỉnh V (đồ thị rất thưa), mặc dù O(VE) vẫn lớn hơn O(E log V), sự khác biệt có thể không quá lớn trong một số trường hợp cụ thể.

Nếu đồ thị chỉ có trọng số không âm, Dijkstra là lựa chọn tốt hơn vì nhanh hơn.

Bài tập ví dụ:

Tuyến đường bay

Trong một dự án về giao thông, FullHouse Dev được giao nhiệm vụ phân tích các tuyến đường bay giữa các thành phố. Họ cần tìm ra \(k\) tuyến đường bay có chi phí thấp nhất từ thành phố Syrjälä đến thành phố Metsälä.

Bài toán

FullHouse Dev cần tìm \(k\) tuyến đường bay ngắn nhất từ Syrjälä đến Metsälä. Một tuyến đường có thể đi qua cùng một thành phố nhiều lần. Lưu ý rằng có thể có nhiều tuyến đường có cùng chi phí và mỗi tuyến đường đều cần được xem xét.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\): số lượng thành phố, số lượng chuyến bay và tham số \(k\). Các thành phố được đánh số từ \(1\) đến \(n\). Thành phố 1 là Syrjälä và thành phố \(n\) là Metsälä.
• \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): chuyến bay bắt đầu từ thành phố \(a\), kết thúc tại thành phố \(b\) và có chi phí là \(c\). Tất cả các chuyến bay đều là một chiều.

OUTPUT FORMAT:

• In ra \(k\) số nguyên: chi phí của \(k\) tuyến đường rẻ nhất được sắp xếp theo thứ tự tăng dần.

Ràng buộc:

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)
• \(1 \leq k \leq 10\)

Ví dụ

INPUT

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

OUTPUT

4 4 7

Giải thích

Các tuyến đường rẻ nhất là:

• \(1 \rightarrow 3 \rightarrow 4\) (chi phí 4)
• \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) (chi phí 4)
• \(1 \rightarrow 2 \rightarrow 4\) (chi phí 7) Okay, đây là hướng dẫn giải bài toán "Tuyến đường bay" bằng C++ mà không cung cấp code hoàn chỉnh:

1. Phân tích bài toán: Bài toán yêu cầu tìm k tuyến đường có chi phí thấp nhất từ thành phố 1 đến thành phố n. Chi phí các chuyến bay là dương, và có thể đi qua cùng một thành phố nhiều lần. Đây là bài toán tìm k đường đi ngắn nhất (K-shortest paths) trên đồ thị có hướng với trọng số không âm.

2. Thuật toán cơ bản: Thuật toán Dijkstra là phương pháp chuẩn để tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. Để tìm k đường đi ngắn nhất, ta cần mở rộng ý tưởng của Dijkstra. Thay vì chỉ lưu khoảng cách ngắn nhất đến mỗi đỉnh, ta sẽ lưu k khoảng cách ngắn nhất đến mỗi đỉnh được tìm thấy cho đến nay.

3. Cấu trúc dữ liệu:

   • Đồ thị: Sử dụng danh sách kề (adjacency list). Mỗi phần tử trong danh sách kề của đỉnh u sẽ là một cặp (v, w) biểu thị có chuyến bay một chiều từ u đến v với chi phí w.
   • Khoảng cách: Đối với mỗi thành phố i (từ 1 đến n), ta cần lưu giữ k chi phí thấp nhất để đến thành phố i được tìm thấy trong quá trình thuật toán chạy. Một cách hiệu quả để lưu trữ và quản lý k giá trị nhỏ nhất là sử dụng một min-priority queue kích thước tối đa k, hoặc dễ cài đặt hơn trong C++ là một max-priority queue kích thước tối đa k. Một max-priority queue cho phép bạn dễ dàng kiểm tra xem một chi phí mới có nhỏ hơn chi phí lớn nhất trong k chi phí hiện tại hay không, và thay thế nếu cần. Sử dụng mảng dist[n+1] trong đó mỗi dist[i] là một max-priority queue chứa các chi phí long long.
   • Hàng đợi ưu tiên cho thuật toán Dijkstra: Sử dụng một priority queue (min-heap) để lưu các trạng thái cần xét, tương tự như Dijkstra chuẩn. Mỗi trạng thái là một cặp (chi phí, thành phố). Priority queue sẽ luôn lấy ra trạng thái có chi phí thấp nhất. Sử dụng priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>.

4. Thuật toán chi tiết (Modified Dijkstra):

   • Khởi tạo mảng dist[n+1]. Mỗi dist[i] là một priority queue rỗng.
   • Khởi tạo hàng đợi ưu tiên chính pq. Thêm trạng thái ban đầu (0, 1) vào pq. Thêm chi phí 0 vào dist[1].
   • Trong khi pq chưa rỗng:
     • Lấy ra trạng thái (d, u) có chi phí d nhỏ nhất từ pq.
     • Kiểm tra loại bỏ: Nếu dist[u] đã chứa k chi phí, và chi phí d vừa lấy ra lớn hơn chi phí lớn nhất trong dist[u] (là phần tử top của max-priority queue dist[u]), thì đường đi này không thể là một trong k đường đi ngắn nhất đến u tốt hơn những cái đã tìm thấy. Bỏ qua trạng thái này và tiếp tục vòng lặp.
     • Duyệt qua tất cả các chuyến bay đi từ thành phố u đến thành phố v với chi phí w.
     • Tính chi phí mới để đến v qua u: new_dist = d + w.
     • Kiểm tra dist[v]:
       • Nếu dist[v] hiện có ít hơn k chi phí: Thêm new_dist vào dist[v]. Thêm trạng thái (new_dist, v) vào pq.
       • Nếu dist[v] hiện có đúng k chi phí: So sánh new_dist với chi phí lớn nhất trong dist[v] (là dist[v].top()). Nếu new_dist nhỏ hơn dist[v].top(), thì new_dist là một trong k chi phí tốt hơn đến v. Xóa chi phí lớn nhất khỏi dist[v] (dist[v].pop()), thêm new_dist vào dist[v] (dist[v].push(new_dist)), và thêm trạng thái (new_dist, v) vào pq.
   • Quá trình kết thúc khi pq rỗng.

5. Kết quả: Sau khi thuật toán chạy xong, dist[n] sẽ chứa k chi phí thấp nhất để đến thành phố n.

   • Kiểm tra xem dist[n] có đủ k phần tử không. Nếu không đủ, nghĩa là chỉ tìm thấy ít hơn k đường đi đến n.
   • Lấy các chi phí từ dist[n] (ví dụ, chuyển chúng vào một vector).
   • Sắp xếp các chi phí này theo thứ tự tăng dần (priority queue max-heap sẽ cho ra thứ tự giảm dần khi pop, nên cần sắp xếp lại).
   • In ra k (hoặc ít hơn nếu không đủ) chi phí này.

6. Lưu ý:

   • Sử dụng kiểu dữ liệu long long cho chi phí vì tổng chi phí có thể vượt quá giới hạn của int.
   • Tham số k nhỏ (k <= 10) là yếu tố quan trọng làm cho thuật toán này hiệu quả.
   • Kích thước của dist[i] không bao giờ vượt quá k.

Làm thêm nhiều bài tập miễn phí tại đây