Khóa học CTDL và GT

Bài 22.5. Bài tập tổng hợp về thuật toán đường đi ngắn nhất

Chào mừng các bạn quay trở lại với series Cấu trúc dữ liệu và Giải thuật! Chúng ta đã dành thời gian tìm hiểu sâu về các thuật toán tìm đường đi ngắn nhất kinh điển như Dijkstra, Bellman-Ford, và Floyd-Warshall. Mỗi thuật toán đều có điểm mạnh và phạm vi ứng dụng riêng, tùy thuộc vào đặc điểm của đồ thị (có trọng số âm hay không, tìm đường đi từ một nguồn hay tất cả các cặp đỉnh).

Trong bài viết này, chúng ta sẽ không đi sâu lại vào lý thuyết từng thuật toán nữa. Thay vào đó, chúng ta sẽ tập trung vào việc vận dụng linh hoạt các kiến thức đã học để giải quyết một số bài toán tổng hợp, thường gặp trong thực tế cũng như trong các kỳ thi lập trình. Mục tiêu là rèn luyện kỹ năng nhận diện bài toán, lựa chọn thuật toán phù hợp và triển khai chúng bằng C++.

Hãy cùng nhau đối mặt với một vài thử thách nhé!

Nhắc lại nhanh: Lựa chọn thuật toán nào?

Trước khi đi vào bài tập, hãy nhớ lại một chút kim chỉ nam giúp chúng ta lựa chọn thuật toán:

1. Đồ thị không trọng số: BFS (Breadth-First Search) tìm đường đi ngắn nhất (theo số cạnh).
2. Đồ thị có trọng số không âm (≥ 0): Dijkstra.
3. Đồ thị có trọng số bất kỳ (có thể âm < 0): Bellman-Ford. Cần kiểm tra chu trình âm.
4. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh: Floyd-Warshall. Hoặc chạy Dijkstra (nếu không có trọng số âm) hoặc Bellman-Ford (nếu có trọng số âm nhưng không có chu trình âm) từ mỗi đỉnh nguồn.

Bây giờ, bắt tay vào giải quyết các bài toán cụ thể!

Bài tập 1: Đường đi rẻ nhất trong mê cung có chi phí

Đề bài: Cho một mê cung dạng lưới kích thước R x C. Mỗi ô (r, c) có một chi phí để bước vào là cost[r][c]. Bạn bắt đầu từ ô (0, 0) và muốn đến ô (R-1, C-1). Bạn chỉ có thể di chuyển sang các ô kề cạnh (lên, xuống, trái, phải), không đi chéo. Tìm tổng chi phí nhỏ nhất để đi từ (0, 0) đến (R-1, C-1).

Phân tích:

• Mê cung dạng lưới có thể được xem như một đồ thị. Mỗi ô (r, c) là một đỉnh.
• Các cạnh nối các ô kề nhau.
• Trọng số của cạnh đến một ô (r, c) chính là cost[r][c]. Trọng số này luôn không âm.
• Đây là bài toán tìm đường đi ngắn nhất từ một nguồn ((0, 0)) đến một đích ((R-1, C-1)) trên đồ thị có trọng số không âm.
• Kết luận: Dijkstra là lựa chọn phù hợp.

Cách tiếp cận:

Chúng ta sẽ biểu diễn lưới dưới dạng đồ thị ngầm định (implicit graph). Các đỉnh là các cặp tọa độ (r, c). Sử dụng thuật toán Dijkstra với hàng đợi ưu tiên để tìm đường đi ngắn nhất. Khoảng cách đến một ô (r, c) sẽ là tổng chi phí tích lũy để đến ô đó.

• Tạo mảng dist[R][C] để lưu chi phí nhỏ nhất đến từng ô, khởi tạo vô cùng.
• Chi phí đến ô bắt đầu dist[0][0] bằng cost[0][0].
• Sử dụng hàng đợi ưu tiên (priority_queue) để lưu các bộ (chi_phi, hang, cot), ưu tiên chi phí nhỏ nhất. Ban đầu thêm (cost[0][0], 0, 0) vào hàng đợi.
• Lặp khi hàng đợi còn phần tử:
  • Lấy ô (r, c) có chi phí nhỏ nhất hiện tại ra.
  • Nếu chi phí lấy ra lớn hơn dist[r][c] đã biết, bỏ qua (đã tìm được đường đi tốt hơn).
  • Xét các ô kề (nr, nc):
    • Nếu (nr, nc) hợp lệ (trong phạm vi lưới):
      • Tính chi phí mới để đến (nr, nc) qua (r, c): new_cost = dist[r][c] + cost[nr][nc].
      • Nếu new_cost < dist[nr][nc]: cập nhật dist[nr][nc] = new_cost và thêm (new_cost, nr, nc) vào hàng đợi ưu tiên.
• Kết quả là dist[R-1][C-1].

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// Cấu trúc để lưu trạng thái trong priority_queue: {cost, {row, col}}
struct State {
    int cost;
    int row;
    int col;

    // Hàm so sánh cho priority_queue (mặc định là max-heap, cần min-heap)
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    vector<vector<int>> cost(R, vector<int>(C));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> cost[i][j];
        }
    }

    // Mảng lưu chi phí nhỏ nhất để đến từng ô
    vector<vector<int>> dist(R, vector<int>(C, INF));

    // Priority queue: {cost, {row, col}}
    priority_queue<State, vector<State>, greater<State>> pq;

    // Bắt đầu từ (0, 0). Chi phí ban đầu là cost[0][0]
    dist[0][0] = cost[0][0];
    pq.push({cost[0][0], 0, 0});

    // Các hướng di chuyển: lên, xuống, trái, phải
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        int current_cost = current.cost;
        int r = current.row;
        int c = current.col;

        // Nếu chi phí hiện tại lớn hơn chi phí đã ghi nhận, bỏ qua
        if (current_cost > dist[r][c]) {
            continue;
        }

        // Xét 4 ô kề
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // Kiểm tra ô kề có hợp lệ không
            if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                int new_cost = dist[r][c] + cost[nr][nc]; // Chi phí đến ô mới

                // Nếu tìm thấy đường đi rẻ hơn
                if (new_cost < dist[nr][nc]) {
                    dist[nr][nc] = new_cost;
                    pq.push({new_cost, nr, nc});
                }
            }
        }
    }

    // Kết quả là chi phí nhỏ nhất đến ô (R-1, C-1)
    cout << dist[R - 1][C - 1] << endl;

    return 0;
}

Giải thích code:

• Chúng ta định nghĩa INF là một giá trị lớn để biểu thị khoảng cách vô cùng ban đầu.
• Struct State giúp lưu trữ thông tin cần thiết trong hàng đợi ưu tiên: chi phí, hàng và cột. Chúng ta overload toán tử > để tạo min-heap (ưu tiên phần tử có cost nhỏ hơn).
• Mảng cost[R][C] lưu chi phí vào mỗi ô, đọc từ input.
• Mảng dist[R][C] lưu chi phí nhỏ nhất từ (0, 0) đến (r, c). Khởi tạo tất cả bằng INF.
• Chi phí đến ô bắt đầu (0, 0) được đặt bằng cost[0][0] và đưa vào priority_queue. Lưu ý rằng trong bài toán này, chi phí để "vào" ô bắt đầu cũng được tính. Nếu đề bài nói chi phí chỉ tính từ bước thứ hai trở đi, dist[0][0] sẽ là 0 và chi phí cộng thêm sẽ là cost[nr][nc]. Tùy thuộc vào cách diễn giải đề bài. Ở đây, chúng ta tính cost[0][0] là chi phí đầu tiên.
• Vòng lặp while (!pq.empty()) là lõi của Dijkstra. Chúng ta liên tục lấy đỉnh có chi phí nhỏ nhất chưa xử lý hoàn toàn ra.
• Mảng dr và dc giúp duyệt qua 4 ô kề một cách dễ dàng.
• Kiểm tra if (current_cost > dist[r][c]) là tối ưu hóa quan trọng trong Dijkstra: nếu chi phí hiện tại lấy ra từ PQ đã lớn hơn chi phí tốt nhất đã được ghi nhận cho đỉnh đó, tức là đã có một đường đi ngắn hơn đến đỉnh này được xử lý trước đó, ta bỏ qua.
• Kiểm tra biên nr >= 0 && nr < R && nc >= 0 && nc < C đảm bảo chúng ta không đi ra ngoài lưới.
• Dòng if (new_cost < dist[nr][nc]) là bước relaxation: nếu tìm thấy đường đi mới đến (nr, nc) thông qua (r, c) mà có tổng chi phí nhỏ hơn dist[nr][nc], ta cập nhật dist[nr][nc] và đẩy (new_cost, nr, nc) vào PQ.
• Cuối cùng, dist[R-1][C-1] chứa chi phí nhỏ nhất đến đích.

Độ phức tạp:

• Số đỉnh V = R * C.
• Số cạnh E tối đa khoảng 4 * R * C (mỗi đỉnh có tối đa 4 cạnh kề).
• Thuật toán Dijkstra với priority_queue có độ phức tạp là O(E log V).
• Trong trường hợp này, độ phức tạp là O(RC log(RC)).

Bài tập 2: Kiểm tra cơ hội kinh doanh chênh lệch giá (Arbitrage)

Đề bài: Bạn được cho một danh sách các loại tiền tệ và tỷ giá hối đoái giữa một số cặp tiền tệ. Bắt đầu với 1 đơn vị của một loại tiền tệ bất kỳ, bạn có thể thực hiện một chuỗi các giao dịch hối đoái. Có tồn tại một chuỗi giao dịch mà sau khi thực hiện, bạn kết thúc với số lượng tiền tệ ban đầu lớn hơn 1 đơn vị hay không?

Phân tích:

• Mỗi loại tiền tệ là một đỉnh trong đồ thị.
• Tỷ giá hối đoái giữa hai loại tiền tệ A và B (rate_A_to_B) có thể được xem là "trọng số" của cạnh từ A đến B.
• Chúng ta muốn tìm một chu trình C1 -> C2 -> ... -> Cn -> C1 sao cho tích của các tỷ giá trên chu trình đó (rate_C1_to_C2 * rate_C2_to_C3 * ... * rate_Cn_to_C1) lớn hơn 1. Đây chính là cơ hội kinh doanh chênh lệch giá (arbitrage).
• Các thuật toán đường đi ngắn nhất thường làm việc với tổng trọng số. Làm sao chuyển bài toán tích sang tổng? Sử dụng logarit!
  • log(a * b * c) = log(a) + log(b) + log(c)
• Nếu chúng ta muốn tìm một chu trình có tích trọng số > 1, điều này tương đương với việc tìm một chu trình có tổng logarit trọng số > log(1) = 0.
• Các thuật toán đường đi ngắn nhất tìm đường đi nhỏ nhất (tổng trọng số nhỏ nhất). Để sử dụng chúng, chúng ta cần biến đổi bài toán tìm tổng logarit lớn nhất thành tìm tổng trọng số nhỏ nhất. Cách đơn giản là nhân các logarit với -1.
• Nếu chúng ta định nghĩa trọng số cạnh từ A đến B là -log(rate_A_to_B), thì tìm một chu trình có tổng trọng số âm (-log(r1) - log(r2) - ... < 0 hay - (log(r1) + log(r2) + ...) < 0 hay log(r1 * r2 * ...) > 0) tương đương với việc tìm một chu trình có tích tỷ giá > 1.
• Bài toán trở thành: Có tồn tại chu trình âm trong đồ thị với trọng số cạnh là -log(tỷ_giá) hay không?
• Đồ thị có thể có trọng số âm (vì tỷ giá có thể nhỏ hơn 1, logarit của nó âm, và nhân -1 thì thành dương; hoặc tỷ giá lớn hơn 1, logarit dương, nhân -1 thành âm).
• Bài toán tìm chu trình âm trên đồ thị có trọng số âm.
• Kết luận: Bellman-Ford là thuật toán thích hợp để phát hiện chu trình âm.

Cách tiếp cận:

• Biểu diễn các loại tiền tệ dưới dạng đỉnh.
• Với mỗi tỷ giá hối đoái rate từ tiền tệ u sang v, tạo cạnh có trọng số -log(rate) từ u đến v. Đồ thị là có hướng.
• Chạy thuật toán Bellman-Ford từ một đỉnh nguồn bất kỳ (hoặc từ tất cả các đỉnh, nhưng chạy từ một đỉnh và kiểm tra tất cả các cạnh ở bước cuối cùng là đủ để phát hiện chu trình âm nếu nó tồn tại và có thể đến được từ nguồn, hoặc đơn giản là chạy Bellman-Ford đủ V-1 bước rồi kiểm tra tất cả các cạnh).
• Nếu sau V-1 bước lặp (trong đó V là số đỉnh), vẫn có thể thực hiện "relaxation" cho bất kỳ cạnh (u, v) với trọng số w (tức là dist[u] + w < dist[v]), điều đó chứng tỏ có một chu trình âm.
• Sự tồn tại của chu trình âm chính là sự tồn tại của cơ hội arbitrage.

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <limits>
#include <map>

using namespace std;

const double INF = numeric_limits<double>::infinity();

struct Edge {
    int from;
    int to;
    double weight; // -log(exchange_rate)
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_currencies, num_rates;
    cin >> num_currencies >> num_rates;

    map<string, int> currency_to_id;
    vector<string> id_to_currency(num_currencies);
    for (int i = 0; i < num_currencies; ++i) {
        cin >> id_to_currency[i];
        currency_to_id[id_to_currency[i]] = i;
    }

    vector<Edge> edges;
    for (int i = 0; i < num_rates; ++i) {
        string u_str, v_str;
        double rate;
        cin >> u_str >> v_str >> rate;
        int u = currency_to_id[u_str];
        int v = currency_to_id[v_str];
        // Trọng số là -log(rate)
        edges.push_back({u, v, -log(rate)});
    }

    // Chọn một đỉnh nguồn bất kỳ (ví dụ đỉnh 0)
    int start_node = 0;
    vector<double> dist(num_currencies, INF);
    dist[start_node] = 0; // Khoảng cách từ nguồn đến chính nó là 0

    // Thuật toán Bellman-Ford: Lặp V-1 lần
    for (int i = 0; i < num_currencies - 1; ++i) {
        bool relaxed = false; // Cờ kiểm tra xem có cạnh nào được nới lỏng không
        for (const auto& edge : edges) {
            if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[edge.from] + edge.weight;
                relaxed = true;
            }
        }
        // Nếu không có cạnh nào được nới lỏng trong một vòng lặp, không có chu trình âm đến được từ nguồn
        // (Tuy nhiên, để chắc chắn phát hiện mọi chu trình âm, ta cứ chạy đủ V-1 lần rồi kiểm tra lần cuối)
        // if (!relaxed && i > 0) break; // Tối ưu nhỏ
    }

    // Bước kiểm tra chu trình âm: Lặp thêm lần thứ V
    bool has_arbitrage = false;
    for (const auto& edge : edges) {
        if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {
            has_arbitrage = true;
            break; // Tìm thấy chu trình âm
        }
    }

    if (has_arbitrage) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Giải thích code:

• Chúng ta sử dụng map để ánh xạ tên tiền tệ (string) sang ID đỉnh (int) và vector<string> để ánh xạ ngược lại.
• struct Edge lưu thông tin cạnh: đỉnh đi (from), đỉnh đến (to) và trọng số (weight). Trọng số được tính là -log(rate).
• Vector edges lưu trữ tất cả các cạnh trong đồ thị.
• Vector dist lưu khoảng cách ngắn nhất từ đỉnh nguồn (đỉnh 0) đến các đỉnh khác. Khởi tạo tất cả bằng INF trừ đỉnh nguồn.
• Vòng lặp chính của Bellman-Ford chạy num_currencies - 1 lần. Trong mỗi lần lặp, chúng ta duyệt qua tất cả các cạnh và thực hiện bước "relaxation": nếu đi từ edge.from sang edge.to với trọng số edge.weight mà có đường đi ngắn hơn đến edge.to so với khoảng cách hiện tại dist[edge.to], ta cập nhật dist[edge.to].
• Sau num_currencies - 1 lần lặp, nếu không có chu trình âm, thuật toán đảm bảo dist chứa khoảng cách ngắn nhất từ nguồn.
• Bước kiểm tra chu trình âm: Lặp thêm một lần nữa qua tất cả các cạnh. Nếu tìm thấy bất kỳ cạnh (u, v) mà vẫn có thể "nới lỏng" (dist[u] + weight < dist[v]), điều đó chứng tỏ có chu trình âm tồn tại và có thể đến được từ nguồn. Do chúng ta chỉ quan tâm sự tồn tại của chu trình âm, không cần biết nó đến được từ nguồn hay không (vì bất kỳ chu trình âm nào cũng cho phép tăng trưởng tiền tệ không giới hạn nếu ta có thể bước vào nó), việc kiểm tra tất cả các cạnh sau V-1 lần lặp là đủ.
• Nếu has_arbitrage là true, in "YES", ngược lại in "NO".

Độ phức tạp:

• Số đỉnh V = num_currencies.
• Số cạnh E = num_rates.
• Thuật toán Bellman-Ford có độ phức tạp là O(V * E).
• Trong trường hợp này, độ phức tạp là O(num_currencies * num_rates).

Bài tập 3: Thời gian di chuyển giữa mọi thành phố

Đề bài: Bạn được cho bản đồ các thành phố và thời gian di chuyển bằng đường bộ giữa một số cặp thành phố trực tiếp. Có thể không có đường trực tiếp giữa mọi cặp. Hãy tìm thời gian di chuyển ngắn nhất giữa mọi cặp thành phố. Thời gian di chuyển luôn không âm.

Phân tích:

• Các thành phố là đỉnh của đồ thị.
• Thời gian di chuyển trực tiếp giữa hai thành phố là trọng số của cạnh nối chúng. Trọng số này luôn không âm.
• Đề bài yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh.
• Kết luận: Floyd-Warshall hoặc chạy Dijkstra từ mỗi đỉnh là phù hợp. Tuy nhiên, Floyd-Warshall thường đơn giản hơn để cài đặt cho bài toán "mọi cặp đỉnh" khi trọng số không âm hoặc chỉ có trọng số âm nhưng không có chu trình âm (trường hợp này trọng số không âm nên Floyd-Warshall an toàn).

Cách tiếp cận (Floyd-Warshall):

Sử dụng thuật toán Floyd-Warshall dựa trên quy hoạch động. Khoảng cách ngắn nhất giữa đỉnh i và đỉnh j chỉ sử dụng các đỉnh từ 0 đến k-1 làm đỉnh trung gian được ký hiệu là dist[i][j][k]. Công thức chuyển đổi trạng thái: dist[i][j][k] = min(dist[i][j][k-1], dist[i][k] + dist[k][j]). Chúng ta có thể tối ưu không gian bằng cách bỏ chiều k và cập nhật tại chỗ trên mảng dist[i][j].

• Khởi tạo ma trận dist[V][V] với giá trị vô cùng cho mọi cặp (i, j) khác nhau, và 0 cho dist[i][i]. Với các cặp (i, j) có đường trực tiếp, cập nhật dist[i][j] bằng thời gian di chuyển trực tiếp.
• Lặp biến trung gian k từ 0 đến V-1.
• Bên trong vòng lặp k, lặp qua tất cả các cặp đỉnh nguồn i (từ 0 đến V-1) và đỉnh đích j (từ 0 đến V-1).
• Cập nhật dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Cẩn thận với trường hợp dist[i][k] hoặc dist[k][j] là vô cùng.

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const long long INF = numeric_limits<long long>::max(); // Sử dụng long long cho INF để tránh tràn số

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_cities;
    cin >> num_cities;

    // Sử dụng ma trận kề để lưu khoảng cách giữa mọi cặp đỉnh
    // dist[i][j] ban đầu là khoảng cách trực tiếp, sau đó là khoảng cách ngắn nhất
    vector<vector<long long>> dist(num_cities, vector<long long>(num_cities, INF));

    // Khởi tạo khoảng cách từ đỉnh đến chính nó là 0
    for (int i = 0; i < num_cities; ++i) {
        dist[i][i] = 0;
    }

    // Đọc input và điền các cạnh trực tiếp
    // Giả sử input cho số lượng cạnh
    int num_roads;
    cin >> num_roads;

    for (int i = 0; i < num_roads; ++i) {
        int u, v;
        long long time;
        cin >> u >> v >> time;
        // Trọng số là thời gian di chuyển
        // Đồ thị có thể là vô hướng nếu đường đi 2 chiều có cùng thời gian,
        // hoặc có hướng nếu khác nhau. Ta giả sử có hướng hoặc vô hướng với cạnh 2 chiều.
        // Nếu vô hướng với cùng thời gian:
        dist[u][v] = min(dist[u][v], time); // Xử lý trường hợp có nhiều đường giữa 2 thành phố, lấy đường ngắn nhất
        dist[v][u] = min(dist[v][u], time);
        // Nếu có hướng: chỉ cần dist[u][v] = min(dist[u][v], time);
    }

    // Thuật toán Floyd-Warshall
    for (int k = 0; k < num_cities; ++k) { // Đỉnh trung gian
        for (int i = 0; i < num_cities; ++i) { // Đỉnh nguồn
            for (int j = 0; j < num_cities; ++j) { // Đỉnh đích
                // Kiểm tra xem có đường đi từ i đến k và từ k đến j không
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    // Cập nhật khoảng cách ngắn nhất từ i đến j thông qua k
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // In kết quả (ma trận khoảng cách ngắn nhất giữa mọi cặp đỉnh)
    // Đối với mỗi cặp (i, j), dist[i][j] là thời gian di chuyển ngắn nhất
    cout << "Shortest travel times between all pairs of cities:" << endl;
    for (int i = 0; i < num_cities; ++i) {
        for (int j = 0; j < num_cities; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF "; // Không có đường đi
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

Giải thích code:

• Chúng ta sử dụng ma trận 2D dist[num_cities][num_cities] để lưu trữ khoảng cách ngắn nhất. Ban đầu, nó được khởi tạo với INF (ngoại trừ dist[i][i] = 0) và sau đó được cập nhật với khoảng cách trực tiếp giữa các thành phố có đường nối. Sử dụng long long cho khoảng cách và INF để tránh tràn số trong trường hợp tổng khoảng cách lớn.
• Ba vòng lặp lồng nhau là cấu trúc chính của Floyd-Warshall. Vòng lặp ngoài cùng (k) cố định đỉnh trung gian được phép sử dụng. Hai vòng lặp trong (i và j) duyệt qua tất cả các cặp đỉnh nguồn-đích.
• Dòng if (dist[i][k] != INF && dist[k][j] != INF) kiểm tra xem có đường đi từ i đến k và từ k đến j hay không trước khi cố gắng cộng chúng lại. Điều này ngăn chặn việc cộng INF với một số khác và gây ra lỗi hoặc kết quả không mong muốn (mặc dù với cách cài đặt này và long long INF, phép cộng INF + INF có thể vẫn là INF hoặc tràn, nên kiểm tra này giúp rõ ràng hơn).
• Dòng dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) là bước "relaxation" DP: khoảng cách ngắn nhất từ i đến j là giá trị hiện tại (không dùng k làm trung gian cuối cùng) hoặc đường đi từ i đến k rồi từ k đến j (sử dụng k làm trung gian cuối cùng).
• Kết quả là ma trận dist, nơi dist[i][j] chứa khoảng cách ngắn nhất từ thành phố i đến thành phố j.

Độ phức tạp:

• Số đỉnh V = num_cities.
• Thuật toán Floyd-Warshall có 3 vòng lặp lồng nhau, mỗi vòng lặp chạy V lần.
• Độ phức tạp là O(V^3).
• Lưu ý: Chạy Dijkstra V lần sẽ có độ phức tạp O(V E log V) hoặc O(V V^2) = O(V^3) nếu dùng ma trận kề. Trong đồ thị dày đặc (E gần V^2), Floyd-Warshall và V lần Dijkstra có độ phức tạp tương đương O(V^3). Trong đồ thị thưa (E << V^2), V lần Dijkstra nhanh hơn O(V E log V). Tuy nhiên, Floyd-Warshall thường dễ cài đặt hơn.

Bài tập 4: Đường đi ngắn nhất trên đồ thị có thêm điều kiện

Đề bài: Cho một đồ thị có trọng số dương. Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T bắt buộc phải đi qua đỉnh V.

Phân tích:

• Đồ thị có trọng số dương.
• Bài toán tìm đường đi ngắn nhất từ S đến T.
• Có thêm điều kiện: phải đi qua đỉnh V.
• Đường đi từ S đến T đi qua V có thể được chia thành hai phần: đường đi từ S đến V, và đường đi từ V đến T.
• Đường đi ngắn nhất từ S đến T đi qua V chính là đường đi ngắn nhất từ S đến V cộng đường đi ngắn nhất từ V đến T.
• Các đường đi con này phải là đường đi ngắn nhất trên đồ thị gốc.
• Vì trọng số dương, chúng ta có thể sử dụng Dijkstra.
• Kết luận: Chạy Dijkstra hai lần.

Cách tiếp cận:

1. Chạy Dijkstra từ đỉnh S để tìm khoảng cách ngắn nhất từ S đến mọi đỉnh khác, bao gồm cả V. Lưu kết quả vào mảng dist_S.
2. Chạy Dijkstra từ đỉnh V để tìm khoảng cách ngắn nhất từ V đến mọi đỉnh khác, bao gồm cả T. Lưu kết quả vào mảng dist_V.
3. Khoảng cách ngắn nhất từ S đến T bắt buộc qua V sẽ là dist_S[V] + dist_V[T]. Cần kiểm tra xem cả hai khoảng cách này có phải là hữu hạn (tức là có đường đi từ S đến V và từ V đến T) không.

Code minh họa (C++):

Sử dụng lại hàm Dijkstra chung.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const long long INF = numeric_limits<long long>::max();

struct Edge {
    int to;
    long long weight;
};

// Hàm Dijkstra chung
vector<long long> dijkstra(int start_node, int num_nodes, const vector<vector<Edge>>>& adj) {
    vector<long long> dist(num_nodes, INF);
    dist[start_node] = 0;

    // priority_queue: {distance, node} (min-heap)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start_node});

    while (!pq.empty()) {
        long long current_dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (current_dist > dist[u]) {
            continue;
        }

        for (const auto& edge : adj[u]) {
            int v = edge.to;
            long long weight = edge.weight;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int num_nodes, num_edges;
    cin >> num_nodes >> num_edges;

    vector<vector<Edge>> adj(num_nodes);
    for (int i = 0; i < num_edges; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // Đồ thị có hướng, hoặc thêm cả 2 chiều nếu vô hướng
        adj[u].push_back({v, w});
        // Nếu vô hướng: adj[v].push_back({u, w});
    }

    int S, T, V; // Nguồn S, Đích T, Điểm trung gian V
    cin >> S >> T >> V;

    // Bước 1: Chạy Dijkstra từ S
    vector<long long> dist_S = dijkstra(S, num_nodes, adj);

    // Bước 2: Chạy Dijkstra từ V
    vector<long long> dist_V = dijkstra(V, num_nodes, adj);

    // Tính tổng khoảng cách
    long long total_dist = INF;
    if (dist_S[V] != INF && dist_V[T] != INF) {
        total_dist = dist_S[V] + dist_V[T];
    }

    // In kết quả
    if (total_dist == INF) {
        cout << "No path from " << S << " to " << T << " via " << V << endl;
    } else {
        cout << "Shortest path from " << S << " to " << T << " via " << V << ": " << total_dist << endl;
    }

    return 0;
}

Giải thích code:

• Chúng ta tạo một hàm dijkstra chung nhận đỉnh nguồn, số lượng đỉnh và danh sách kề của đồ thị, trả về vector chứa khoảng cách ngắn nhất từ nguồn đến mọi đỉnh khác. Cài đặt này là Dijkstra cơ bản sử dụng priority_queue.
• Trong main, chúng ta đọc đồ thị và ba đỉnh S, T, V.
• Gọi hàm dijkstra lần thứ nhất từ đỉnh S để tính dist_S.
• Gọi hàm dijkstra lần thứ hai từ đỉnh V để tính dist_V.
• Kết quả cần tìm là dist_S[V] + dist_V[T]. Chúng ta kiểm tra xem cả dist_S[V] và dist_V[T] có phải là INF không. Nếu bất kỳ giá trị nào là INF, tức là không có đường đi từ S đến V hoặc từ V đến T, thì không có đường đi từ S đến T qua V, và kết quả là INF.
• In kết quả cuối cùng.

Độ phức tạp:

• Thuật toán Dijkstra với priority_queue có độ phức tạp O(E log V).
• Chúng ta chạy Dijkstra 2 lần.
• Tổng độ phức tạp là O(E log V). Đây là hiệu quả hơn đáng kể so với O(V^3) nếu đồ thị thưa.

Bài tập ví dụ:

Đường đi ngắn nhất II

Trong quá trình quy hoạch một khu đô thị mới, FullHouse Dev được giao nhiệm vụ tính toán các tuyến đường ngắn nhất giữa các khu vực.

Bài toán

Có \(n\) thành phố và \(m\) con đường nối giữa chúng. Nhiệm vụ của bạn là xử lý \(q\) truy vấn, mỗi truy vấn yêu cầu xác định độ dài của đường đi ngắn nhất giữa hai thành phố cho trước.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(q\): số lượng thành phố, số lượng con đường và số lượng truy vấn.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): có một con đường hai chiều giữa thành phố \(a\) và thành phố \(b\) với độ dài \(c\).
• \(q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(a\) và \(b\): yêu cầu tìm độ dài đường đi ngắn nhất giữa thành phố \(a\) và thành phố \(b\).

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra độ dài của đường đi ngắn nhất. Nếu không tồn tại đường đi, in ra -1.

Ràng buộc:

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

Ví dụ:

INPUT

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

OUTPUT

5
5
8
-1
3

Giải thích:

• Với truy vấn 1 và 2: Đường đi ngắn nhất giữa thành phố 1 và 2 (hoặc ngược lại) có độ dài 5.
• Với truy vấn 3: Đường đi ngắn nhất từ 1 đến 3 có độ dài 8 (đi từ 1 → 2 → 3).
• Với truy vấn 4: Không có đường đi từ thành phố 1 đến 4.
• Với truy vấn 5: Đường đi ngắn nhất từ 3 đến 2 có độ dài 3. Tuyệt vời, bài toán này là một dạng kinh điển về tìm đường đi ngắn nhất trên đồ thị. Với ràng buộc n nhỏ (\leq 500) và q lớn (\leq 10^5), việc chạy thuật toán tìm đường đi ngắn nhất từ một điểm phát (như Dijkstra) cho mỗi truy vấn sẽ rất chậm. Thay vào đó, ta nên sử dụng thuật toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh (All-Pairs Shortest Path) một lần duy nhất, sau đó trả lời các truy vấn trong thời gian O(1).

Thuật toán phù hợp nhất trong trường hợp này là Thuật toán Floyd-Warshall.

Hướng giải chi tiết (không bao gồm code hoàn chỉnh):

1. Khởi tạo ma trận khoảng cách:

   • Tạo một ma trận dist[n+1][n+1] (hoặc kích thước phù hợp với chỉ số 1-based).
   • Khởi tạo dist[i][i] = 0 cho mọi i từ 1 đến n.
   • Khởi tạo dist[i][j] bằng một giá trị "vô cùng lớn" (LLONG_MAX trong C++ long long hoặc một giá trị đủ lớn như 1e15) cho i \neq j. Giá trị này biểu thị rằng ban đầu chưa có đường đi giữa i và j.
   • Đọc m cạnh. Với mỗi cạnh a, b, c: cập nhật dist[a][b] = min(dist[a][b], c) và dist[b][a] = min(dist[b][a], c) (vì đường đi hai chiều). Chú ý trường hợp có nhiều cạnh giữa cùng một cặp đỉnh, ta chỉ lấy cạnh có trọng số nhỏ nhất.

2. Áp dụng thuật toán Floyd-Warshall:

   • Sử dụng ba vòng lặp lồng nhau:
     • Vòng ngoài cùng cho đỉnh trung gian k từ 1 đến n.
     • Hai vòng trong cho đỉnh bắt đầu i từ 1 đến n và đỉnh kết thúc j từ 1 đến n.
   • Bên trong các vòng lặp, cập nhật dist[i][j] bằng công thức: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
     • Lưu ý: Khi tính dist[i][k] + dist[k][j], cần kiểm tra xem cả dist[i][k] và dist[k][j] có phải là "vô cùng lớn" hay không để tránh tràn số hoặc cộng với vô cùng. Chỉ thực hiện phép cộng nếu cả hai đều hữu hạn.
   • Sử dụng kiểu dữ liệu long long cho ma trận khoảng cách để tránh tràn số, vì trọng số có thể lên đến 10^9 và đường đi có thể bao gồm nhiều cạnh.

3. Trả lời truy vấn:

   • Sau khi chạy xong thuật toán Floyd-Warshall, ma trận dist chứa độ dài đường đi ngắn nhất giữa mọi cặp đỉnh.
   • Với mỗi truy vấn a, b:
     • Kiểm tra dist[a][b].
     • Nếu dist[a][b] vẫn bằng giá trị "vô cùng lớn" ban đầu, in ra -1 (không có đường đi).
     • Ngược lại, in ra dist[a][b].

Tóm tắt:

• Sử dụng thuật toán APSP: Floyd-Warshall.
• Ma trận khoảng cách dist kích thước O(N^2), kiểu dữ liệu long long.
• Khởi tạo dist[i][j] với 0 cho i=j, vô cùng cho i \neq j, và cập nhật trực tiếp từ các cạnh ban đầu.
• Ba vòng lặp O(N^3) để cập nhật ma trận dist.
• Mỗi truy vấn O(1) bằng cách tra cứu giá trị trong ma trận dist.
• Tổng thời gian: O(N^3 + Q). Với N=500, N^3 là khoảng 1.25e8, chấp nhận được.

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