Bài 22.2: Thuật toán Dijkstra và cài đặt hiệu quả

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ đi sâu vào một trong những thuật toán kinh điển và quan trọng nhất trong lý thuyết đồ thị: Thuật toán Dijkstra. Thuật toán này được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số với các cạnh có trọng số không âm.

Bài toán: Tìm đường đi ngắn nhất một nguồn

Hãy tưởng tượng bạn đang ở một thành phố và muốn tìm đường đi ngắn nhất (dựa trên khoảng cách, thời gian hoặc chi phí) từ vị trí hiện tại của mình (đỉnh nguồn) đến tất cả các địa điểm quan trọng khác trong thành phố (các đỉnh còn lại). Đây chính là bài toán tìm đường đi ngắn nhất một nguồn.

Trong ngữ cảnh đồ thị, chúng ta có một đồ thị G = (V, E), trong đó V là tập hợp các đỉnh (địa điểm) và E là tập hợp các cạnh (tuyến đường). Mỗi cạnh (u, v) có một trọng số w(u, v), biểu thị "chi phí" đi từ u đến v. Trọng số này có thể là khoảng cách, thời gian di chuyển, chi phí xăng, v.v. Điều kiện tiên quyết cực kỳ quan trọng để Dijkstra hoạt động đúng là tất cả các trọng số trên cạnh phải là số không âm (w(u, v) >= 0).

Mục tiêu của chúng ta là, cho một đỉnh nguồn s ∈ V, tìm đường đi có tổng trọng số nhỏ nhất từ s đến mọi đỉnh v ∈ V. Tổng trọng số của một đường đi là tổng trọng số của tất cả các cạnh trên đường đi đó.

Tại sao lại là Dijkstra?

Có nhiều thuật toán giải quyết bài toán tìm đường đi ngắn nhất. Ví dụ:

BFS (Breadth-First Search): Tìm đường đi ngắn nhất trên đồ thị không có trọng số (hoặc coi tất cả trọng số đều bằng 1).
Bellman-Ford: Tìm đường đi ngắn nhất trên đồ thị có thể có trọng số âm, nhưng sẽ phát hiện chu trình âm (nếu có). Tuy nhiên, Bellman-Ford chậm hơn Dijkstra.
Floyd-Warshall: Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Dijkstra tỏa sáng khi bạn cần tìm đường đi ngắn nhất từ một nguồn duy nhất và biết chắc chắn rằng không có cạnh nào có trọng số âm. Nó hiệu quả hơn Bellman-Ford cho trường hợp này.

Ý tưởng cốt lõi của thuật toán Dijkstra

Dijkstra là một thuật toán tham lam (greedy). Nó hoạt động dựa trên ý tưởng mở rộng dần phạm vi "đã biết" đường đi ngắn nhất từ đỉnh nguồn.

Hãy hình dung bạn đang lan tỏa một "làn sóng" từ đỉnh nguồn. Làn sóng này sẽ chạm tới các đỉnh gần nhất trước, sau đó đến các đỉnh xa hơn, và cứ thế tiếp tục.

Tại mỗi bước, thuật toán sẽ:

Chọn đỉnh u chưa được xử lý (chưa nằm trong tập các đỉnh mà chúng ta đã xác định được đường đi ngắn nhất cuối cùng từ nguồn đến chúng) có khoảng cách hiện tại được ước lượng từ đỉnh nguồn là nhỏ nhất.
Đánh dấu đỉnh u là đã được xử lý.
Kiểm tra tất cả các đỉnh v là hàng xóm của u. Đối với mỗi hàng xóm v, chúng ta thử "thư giãn" (relax) cạnh (u, v). Nghĩa là, chúng ta kiểm tra xem liệu đi từ nguồn đến u rồi đi tiếp cạnh (u, 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 mà chúng ta đang có cho v hay không.
- Nếu khoảng cách từ nguồn đến u + trọng số cạnh (u, v) < khoảng cách hiện tại từ nguồn đến v
- Thì chúng ta cập nhật khoảng cách hiện tại từ nguồn đến v = khoảng cách từ nguồn đến u + trọng số cạnh (u, v) và ghi nhận rằng đường đi ngắn nhất đến v hiện tại đi qua u.

Thuật toán lặp lại quá trình này cho đến khi tất cả các đỉnh đều đã được xử lý (hoặc không thể đến được).

Tại sao nó hoạt động với trọng số không âm? Điều kiện trọng số không âm đảm bảo rằng khi chúng ta chọn đỉnh u có khoảng cách nhỏ nhất trong số các đỉnh chưa xử lý, thì khoảng cách đó chắc chắn là khoảng cách ngắn nhất cuối cùng từ nguồn đến u. Bởi vì nếu có một đường đi ngắn hơn đến u, thì đường đi đó phải đi qua một đỉnh v nào đó chưa được xử lý. Nhưng nếu v chưa được xử lý và có thể dẫn đến một đường đi ngắn hơn đến u, thì khoảng cách đến v phải nhỏ hơn hoặc bằng khoảng cách đến u (do không có cạnh âm làm giảm tổng trọng số). Điều này mâu thuẫn với việc chúng ta đã chọn u là đỉnh có khoảng cách nhỏ nhất trong số các đỉnh chưa xử lý. Do đó, khoảng cách đến u đã được xác định là tối ưu.

Các bước chi tiết của thuật toán Dijkstra

Khởi tạo:
- Tạo một mảng (hoặc map) dist để lưu trữ khoảng cách ngắn nhất hiện tại được ước lượng từ đỉnh nguồn đến mỗi đỉnh. Khởi tạo dist[s] = 0 cho đỉnh nguồn s, và dist[v] = INF (vô cùng lớn) cho tất cả các đỉnh v khác (cho biết ban đầu chúng ta chưa biết đường đi đến các đỉnh này).
- Tạo một tập hợp (hoặc mảng boolean) visited để theo dõi các đỉnh đã được xử lý (đã xác định được đường đi ngắn nhất cuối cùng đến chúng). Khởi tạo tất cả là false.
- (Để cài đặt hiệu quả) Sử dụng một cấu trúc dữ liệu hàng đợi ưu tiên (Priority Queue) để lưu trữ các cặp {khoảng cách, đỉnh}. Ban đầu, thêm cặp {0, s} vào hàng đợi ưu tiên. Hàng đợi ưu tiên sẽ tự động giữ đỉnh có khoảng cách nhỏ nhất lên đầu.
Lặp:
- Trong khi hàng đợi ưu tiên còn phần tử:
  - Trích xuất (lấy ra) đỉnh u từ hàng đợi ưu tiên mà có khoảng cách hiện tại (dist[u]) là nhỏ nhất.
  - Nếu đỉnh u đã được xử lý (visited[u] là true), bỏ qua và tiếp tục vòng lặp (vì chúng ta đã tìm được đường đi ngắn nhất đến u trước đó rồi).
  - Đánh dấu đỉnh u là đã được xử lý (visited[u] = true).
  - Đối với mỗi hàng xóm v của u và cạnh (u, v) có trọng số w:
    - Kiểm tra xem liệu dist[u] + w có nhỏ hơn dist[v] hay không.
    - Nếu có (dist[u] + w < dist[v]):
      - Cập nhật dist[v] = dist[u] + w.
      - Thêm cặp {dist[v], v} vào hàng đợi ưu tiên. (Lưu ý: có thể có nhiều mục nhập cho cùng một đỉnh v trong PQ, nhưng mục nhập có khoảng cách nhỏ nhất sẽ được xử lý trước).
Kết quả: Sau khi vòng lặp kết thúc, mảng dist sẽ chứa khoảng cách ngắn nhất từ đỉnh nguồn s đến tất cả các đỉnh khác. Nếu dist[v] vẫn là INF, nghĩa là không có đường đi từ s đến v.

Cài đặt hiệu quả bằng C++ sử dụng Priority Queue

Việc sử dụng Priority Queue là chìa khóa để cải thiện hiệu quả của thuật toán Dijkstra. Thay vì phải quét qua tất cả các đỉnh chưa xử lý để tìm đỉnh có khoảng cách nhỏ nhất ở mỗi bước (Naive Dijkstra O(V^2)), Priority Queue giúp chúng ta tìm đỉnh này một cách nhanh chóng (logarit thời gian).

Chúng ta sẽ biểu diễn đồ thị bằng danh sách kề (Adjacency List). Mỗi phần tử trong danh sách kề sẽ là một cặp {đỉnh đích, trọng số}. Priority Queue sẽ lưu trữ các cặp {khoảng cách, đỉnh}, và chúng ta cần nó hoạt động như một min-heap (lấy phần tử nhỏ nhất ra trước). Trong C++ STL, std::priority_queue mặc định là max-heap. Để biến nó thành min-heap cho cặp {khoảng cách, đỉnh}, chúng ta cần sử dụng std::greater<pair<int, int>>.

Đây là cấu trúc dữ liệu:

adj: vector<pair<int, int>> adj[N] - Danh sách kề, adj[u] chứa danh sách các cặp {v, w} cho biết có cạnh từ u đến v với trọng số w.
dist: vector<int> dist(N, INF) - Mảng khoảng cách.
pq: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq - Hàng đợi ưu tiên, lưu trữ các cặp {khoảng cách, đỉnh}, sắp xếp theo khoảng cách tăng dần.

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

using namespace std;

const int INF = numeric_limits<int>::max(); // Sử dụng giá trị INT_MAX làm vô cùng

// Hàm thực hiện thuật toán Dijkstra
// graph: danh sách kề biểu diễn đồ thị (adj[u] = list of pairs {v, weight})
// n: số đỉnh của đồ thị (đỉnh từ 0 đến n-1)
// start_node: đỉnh nguồn
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int n, int start_node) {
    // Mảng lưu trữ khoảng cách ngắn nhất từ start_node đến mỗi đỉnh
    vector<int> dist(n, INF);

    // Hàng đợi ưu tiên, lưu trữ cặp {khoảng cách, đỉnh}
    // Sử dụng std::greater để có min-heap (lấy phần tử có khoảng cách nhỏ nhất ra trước)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // Khởi tạo khoảng cách đến đỉnh nguồn là 0
    dist[start_node] = 0;

    // Thêm đỉnh nguồn vào hàng đợi ưu tiên
    pq.push({0, start_node});

    // Mảng đánh dấu các đỉnh đã được xử lý (đã tìm thấy đường đi ngắn nhất cuối cùng)
    // bool visited[n] = {false}; // Cách khác: có thể không cần mảng visited tường minh
                                  // nếu kiểm tra dist[u] > current_distance trong pq

    while (!pq.empty()) {
        // Lấy đỉnh có khoảng cách nhỏ nhất từ hàng đợi ưu tiên
        int current_distance = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // Đây là bước kiểm tra "lười biếng" thay cho mảng visited.
        // Nếu khoảng cách vừa lấy ra từ PQ lớn hơn khoảng cách đã biết đến u
        // thì đây là một entry cũ (stale entry) đã được cập nhật tốt hơn trước đó,
        // chúng ta bỏ qua nó.
        if (current_distance > dist[u]) {
            continue;
        }

        // Duyệt qua tất cả các hàng xóm của u
        for (auto& edge : graph[u]) {
            int v = edge.first; // Đỉnh đích
            int weight = edge.second; // Trọng số cạnh (u, v)

            // Thư giãn (Relax) cạnh (u, v)
            // Nếu đi từ nguồn đến u rồi đến v ngắn hơn đường đi đã biết đến v
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                // Cập nhật khoảng cách đến v
                dist[v] = dist[u] + weight;

                // Thêm/cập nhật v vào hàng đợi ưu tiên với khoảng cách mới
                pq.push({dist[v], v});
            }
        }
    }

    // Trả về mảng khoảng cách
    return dist;
}

// Hàm main để thử nghiệm
int main() {
    int n = 5; // Số đỉnh (đỉnh từ 0 đến 4)
    int m = 7; // Số cạnh

    // Biểu diễn đồ thị bằng danh sách kề
    // graph[i] chứa danh sách các cặp {đỉnh_đích, trọng_số} cho các cạnh đi ra từ đỉnh i
    vector<vector<pair<int, int>>> graph(n);

    // Thêm các cạnh vào đồ thị (đồ thị vô hướng trong ví dụ này, nên thêm 2 chiều)
    // Nếu là đồ thị có hướng, chỉ cần thêm 1 chiều
    graph[0].push_back({1, 10}); // cạnh 0 -> 1, trọng số 10
    graph[0].push_back({2, 3});  // cạnh 0 -> 2, trọng số 3
    graph[1].push_back({2, 1});  // cạnh 1 -> 2, trọng số 1
    graph[1].push_back({3, 2});  // cạnh 1 -> 3, trọng số 2
    graph[2].push_back({1, 4});  // cạnh 2 -> 1, trọng số 4
    graph[2].push_back({3, 8});  // cạnh 2 -> 3, trọng số 8
    graph[2].push_back({4, 2});  // cạnh 2 -> 4, trọng số 2
    graph[3].push_back({4, 5});  // cạnh 3 -> 4, trọng số 5

    // Để đồ thị vô hướng, thêm các cạnh ngược lại:
    graph[1].push_back({0, 10});
    graph[2].push_back({0, 3});
    graph[2].push_back({1, 1});
    graph[3].push_back({1, 2});
    graph[1].push_back({2, 4});
    graph[3].push_back({2, 8});
    graph[4].push_back({2, 2});
    graph[4].push_back({3, 5});
    // Lưu ý: Với đồ thị vô hướng, thường có thể đơn giản hóa việc thêm cạnh nếu sử dụng cấu trúc phù hợp.
    // Ở đây, để minh họa rõ ràng danh sách kề, ta thêm tường minh.
    // Trong thực tế, khi đọc input đồ thị vô hướng, ta thêm cả {v,w} vào adj[u] và {u,w} vào adj[v].

    int start_node = 0; // Bắt đầu từ đỉnh 0

    // Chạy thuật toán Dijkstra
    vector<int> shortest_distances = dijkstra(graph, n, start_node);

    // In kết quả
    cout << "Khoang cach ngan nhat tu dinh " << start_node << " den cac dinh khac:" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "Den dinh " << i << ": ";
        if (shortest_distances[i] == INF) {
            cout << "Khong the den";
        } else {
            cout << shortest_distances[i];
        }
        cout << endl;
    }

    return 0;
}

Giải thích Code C++

#include <iostream>, <vector>, <queue>, <limits>: Các thư viện cần thiết cho nhập xuất, sử dụng vector, priority_queue, và giới hạn số nguyên (INT_MAX).
const int INF = numeric_limits<int>::max();: Định nghĩa một hằng số INF biểu thị vô cùng, sử dụng giá trị lớn nhất có thể của kiểu int. Điều này quan trọng để khởi tạo khoảng cách ban đầu cho các đỉnh chưa biết đường đi.
vector<vector<pair<int, int>>> graph: Đây là danh sách kề để biểu diễn đồ thị. graph[u] là một vector chứa các pair<int, int>, mỗi pair là {v, w} thể hiện có một cạnh từ u đến v với trọng số w.
vector<int> dist(n, INF): Mảng dist kích thước n (số đỉnh). dist[i] sẽ lưu trữ khoảng cách ngắn nhất từ đỉnh nguồn đến đỉnh i. Ban đầu, tất cả được khởi tạo là INF, trừ đỉnh nguồn.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;: Đây là hàng đợi ưu tiên. Nó lưu trữ các cặp {khoảng cách, đỉnh}. std::greater<pair<int, int>> là một comparator chỉ định rằng hàng đợi này là min-heap dựa trên phần tử đầu tiên của cặp (khoảng cách).
Khởi tạo:
- dist[start_node] = 0;: Khoảng cách từ đỉnh nguồn đến chính nó là 0.
- pq.push({0, start_node});: Đưa đỉnh nguồn vào hàng đợi ưu tiên với khoảng cách 0.
Vòng lặp chính while (!pq.empty()): Thuật toán tiếp tục cho đến khi không còn đỉnh nào trong hàng đợi ưu tiên để xử lý.
Trích xuất đỉnh:
- int current_distance = pq.top().first;
- int u = pq.top().second;
- pq.pop();
- Lấy đỉnh u có khoảng cách current_distance nhỏ nhất ra khỏi PQ.
Kiểm tra "Stale Entry": if (current_distance > dist[u]) { continue; }: Đây là một kỹ thuật tối ưu khi sử dụng PQ. Một đỉnh có thể được thêm vào PQ nhiều lần với các khoảng cách khác nhau do quá trình thư giãn. Khi lấy một đỉnh u ra khỏi PQ, chúng ta kiểm tra xem khoảng cách current_distance đó có vẫn là khoảng cách ngắn nhất đã biết đến u trong mảng dist hay không. Nếu current_distance > dist[u], điều đó có nghĩa là chúng ta đã tìm thấy một đường đi ngắn hơn đến u thông qua một đường khác và đã cập nhật dist[u] rồi. Mục nhập này trong PQ là cũ và không còn giá trị, nên chúng ta bỏ qua.
Duyệt hàng xóm và Thư giãn (Relaxation):
- Vòng lặp for (auto& edge : graph[u]) duyệt qua tất cả các cạnh đi ra từ đỉnh u.
- int v = edge.first; int weight = edge.second;: Lấy thông tin về đỉnh đích v và trọng số weight của cạnh (u, v).
- if (dist[u] != INF && dist[u] + weight < dist[v]): Điều kiện kiểm tra thư giãn. Nếu đường đi từ nguồn đến u là khả thi (dist[u] != INF) và tổng khoảng cách đi từ nguồn đến u rồi đến v (dist[u] + weight) nhỏ hơn khoảng cách ngắn nhất hiện tại đến v (dist[v]), thì chúng ta tìm thấy một đường đi ngắn hơn đến v.
- dist[v] = dist[u] + weight;: Cập nhật khoảng cách ngắn nhất đến v.
- pq.push({dist[v], v});: Đưa đỉnh v vào hàng đợi ưu tiên với khoảng cách mới cập nhật.

Ví dụ minh họa (Trên đồ thị trong code)

Đồ thị ví dụ:

5 đỉnh: 0, 1, 2, 3, 4
Các cạnh (trọng số): (0,1:10), (0,2:3), (1,2:1), (1,3:2), (2,1:4), (2,3:8), (2,4:2), (3,4:5)
Đỉnh nguồn: 0

Quá trình chạy (minh họa một phần):

Khởi tạo:
- dist = {0, INF, INF, INF, INF}
- pq = {{0, 0}}
Bước 1:
- Lấy {0, 0} từ PQ. u = 0, current_distance = 0.
- dist[0] là 0, current_distance không lớn hơn dist[0]. Tiếp tục.
- Duyệt hàng xóm của 0:
  - Cạnh (0, 1) trọng số 10: dist[0] + 10 = 0 + 10 = 10. 10 < dist[1] (INF). Cập nhật dist[1] = 10. Push {10, 1} vào PQ.
  - Cạnh (0, 2) trọng số 3: dist[0] + 3 = 0 + 3 = 3. 3 < dist[2] (INF). Cập nhật dist[2] = 3. Push {3, 2} vào PQ.
- PQ bây giờ có: {{3, 2}, {10, 1}} (thứ tự có thể khác tùy cài đặt PQ nhưng {3,2} sẽ ở đầu).
Bước 2:
- Lấy {3, 2} từ PQ. u = 2, current_distance = 3.
- dist[2] là 3, current_distance không lớn hơn dist[2]. Tiếp tục.
- Duyệt hàng xóm của 2:
  - Cạnh (2, 1) trọng số 4: dist[2] + 4 = 3 + 4 = 7. 7 < dist[1] (hiện là 10). Cập nhật dist[1] = 7. Push {7, 1} vào PQ.
  - Cạnh (2, 3) trọng số 8: dist[2] + 8 = 3 + 8 = 11. 11 < dist[3] (INF). Cập nhật dist[3] = 11. Push {11, 3} vào PQ.
  - Cạnh (2, 4) trọng số 2: dist[2] + 2 = 3 + 2 = 5. 5 < dist[4] (INF). Cập nhật dist[4] = 5. Push {5, 4} vào PQ.
- PQ bây giờ có: {{5, 4}, {7, 1}, {10, 1}, {11, 3}}. (Lưu ý: Đỉnh 1 xuất hiện 2 lần, nhưng entry {7,1} sẽ được ưu tiên).
Bước 3:
- Lấy {5, 4} từ PQ. u = 4, current_distance = 5.
- dist[4] là 5, không lớn hơn. Tiếp tục.
- Duyệt hàng xóm của 4:
  - Cạnh (4, 2) trọng số 2: dist[4] + 2 = 5 + 2 = 7. 7 > dist[2] (hiện là 3). Không cập nhật.
  - Cạnh (4, 3) trọng số 5: dist[4] + 5 = 5 + 5 = 10. 10 < dist[3] (hiện là 11). Cập nhật dist[3] = 10. Push {10, 3} vào PQ.
- PQ bây giờ có: {{7, 1}, {10, 1}, {10, 3}, {11, 3}}.
Bước 4:
- Lấy {7, 1} từ PQ. u = 1, current_distance = 7.
- dist[1] là 7, không lớn hơn. Tiếp tục.
- Duyệt hàng xóm của 1:
  - Cạnh (1, 0) trọng số 10: dist[1] + 10 = 7 + 10 = 17. 17 > dist[0] (hiện là 0). Không cập nhật.
  - Cạnh (1, 2) trọng số 1: dist[1] + 1 = 7 + 1 = 8. 8 > dist[2] (hiện là 3). Không cập nhật.
  - Cạnh (1, 3) trọng số 2: dist[1] + 2 = 7 + 2 = 9. 9 < dist[3] (hiện là 10). Cập nhật dist[3] = 9. Push {9, 3} vào PQ.
- PQ bây giờ có: {{9, 3}, {10, 1}, {10, 3}, {11, 3}}. (Lưu ý: Đỉnh 3 xuất hiện 3 lần với các khoảng cách khác nhau).

Quá trình tiếp tục cho đến khi PQ rỗng. Cuối cùng, mảng dist sẽ chứa các khoảng cách ngắn nhất.

Kết quả chạy code ví dụ:

Khoang cach ngan nhat tu dinh 0 den cac dinh khac:
Den dinh 0: 0
Den dinh 1: 7
Den dinh 2: 3
Den dinh 3: 9
Den dinh 4: 5

Các khoảng cách này khớp với quá trình mô phỏng.

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

Độ phức tạp thời gian của thuật toán Dijkstra với Priority Queue sử dụng danh sách kề là O((E + V) log V), trong đó V là số đỉnh và E là số cạnh.

Mỗi cạnh E có thể được duyệt qua một vài lần (tối đa bằng số lần nó được dùng để cập nhật khoảng cách ngắn hơn), và mỗi lần cập nhật có thể dẫn đến việc thêm một phần tử vào PQ, mất thời gian O(log V). Tổng cộng cho các thao tác push là O(E log V).
Mỗi đỉnh V được trích xuất từ PQ tối đa một lần sau khi khoảng cách ngắn nhất đến nó được xác định lần đầu tiên (nhờ kiểm tra current_distance > dist[u]). Thao tác trích xuất pq.pop() mất thời gian O(log V). Tổng cộng cho các thao tác pop là O(V log V).
Độ phức tạp tổng cộng là O(E log V + V log V). Trong các đồ thị liên thông, thường E >= V-1, nên có thể viết gọn thành O(E log V) (do E log V thường trội hơn V log V).

Độ phức tạp không gian là O(V + E) để lưu trữ đồ thị bằng danh sách kề và mảng khoảng cách dist, cộng thêm O(V) cho hàng đợi ưu tiên (trong trường hợp xấu nhất, PQ có thể chứa tới V phần tử). Tổng cộng là O(V + E).

So với cài đặt Dijkstra đơn giản (không dùng PQ) có độ phức tạp O(V^2), việc sử dụng Priority Queue mang lại hiệu quả rõ rệt, đặc biệt với các đồ thị thưa (E << V^2).

Bài tập ví dụ:

Vượt Sông

Trong một ngày đẹp trời, FullHouse Dev đang quan sát một tổ kiến đang tìm cách vượt sông. Các chú kiến không thể bơi qua dòng sông vì dòng chảy quá mạnh. May mắn thay, trên sông có một số hòn đá, và các chú kiến cần tìm ra cách sử dụng chúng để vượt sông an toàn.

Bài toán

Dòng sông nằm trên trục \(X\) và được giới hạn bởi tọa độ \(Y\). Có \(N\) hòn đá, mỗi hòn đá được xác định bởi tọa độ tâm và bán kính. Các chú kiến đang đứng ở bờ sông \(X = 0\). Chúng không thể nhảy giữa các hòn đá nhưng có thể di chuyển từ đá này sang đá khác nếu hai hòn đá có điểm giao nhau. Nhiệm vụ là xác định xem liệu các chú kiến có thể vượt sông hay không, và nếu có thì cần ít nhất bao nhiêu hòn đá.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
Với mỗi test case:
- Dòng đầu chứa số nguyên \(N\) - số lượng hòn đá
- \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(X_i\), \(Y_i\), \(R_i\) trong đó \((X_i, Y_i)\) là tọa độ tâm và \(R_i\) là bán kính của hòn đá
- Dòng cuối chứa hai số nguyên \(U\) và \(L\) - giới hạn trên và dưới của dòng sông

OUTPUT FORMAT:

Với mỗi test case, in ra số lượng hòn đá tối thiểu cần dùng để vượt sông. Nếu không thể vượt sông, in ra \(-1\).

Ràng buộc:

\(1 \leq T \leq 10\)
\(1 \leq N \leq 1000\)
\(-1000 \leq X_i, Y_i \leq 1000\)
\(1 \leq R_i \leq 1000\)
\(-1000 \leq L < U \leq 1000\)

Ví dụ

INPUT

OUTPUT

Giải thích

Từ bờ sông, các chú kiến có thể bước lên hòn đá đầu tiên. Sau đó có thể vượt sông trực tiếp hoặc di chuyển qua hòn đá thứ hai rồi vượt sông. Lưu ý rằng không thể sử dụng hòn đá thứ ba vì nó nằm ngoài tầm với của các hòn đá khác. Đây là hướng dẫn giải bài "Vượt Sông" một cách ngắn gọn:

Mô hình hóa bài toán thành đồ thị:
- Coi mỗi hòn đá là một đỉnh của đồ thị.
- Có một "đỉnh nguồn" ảo representing bờ sông X=0 và một "đỉnh đích" ảo representing bờ sông X >= U.
Xác định các cạnh (Kết nối):
- Kiểm tra xem một hòn đá có thể sử dụng được không: Một hòn đá tâm (X_i, Y_i) bán kính R_i chỉ hữu ích nếu nó nằm trong hoặc giao với phạm vi Y của dòng sông [L, U]. Điều này xảy ra nếu Y_i - R_i <= U và Y_i + R_i >= L. Chỉ xem xét các hòn đá thỏa mãn điều kiện này.
- Cạnh từ Nguồn đến Đá: Có cạnh từ đỉnh nguồn đến hòn đá i (thỏa mãn điều kiện hữu ích Y) nếu hòn đá đó chạm vào hoặc vượt qua đường X=0. Điều này xảy ra nếu X_i - R_i <= 0.
- Cạnh giữa hai Đá: Có cạnh giữa hòn đá i và hòn đá j (đều thỏa mãn điều kiện hữu ích Y) nếu hai hòn đá này giao nhau. Hai hình tròn giao nhau nếu khoảng cách giữa tâm của chúng nhỏ hơn hoặc bằng tổng bán kính. Khoảng cách tâm là sqrt((X_i - X_j)^2 + (Y_i - Y_j)^2). Điều kiện giao nhau là (X_i - X_j)^2 + (Y_i - Y_j)^2 <= (R_i + R_j)^2. Sử dụng bình phương để tránh căn bậc hai và làm việc với số nguyên.
- Cạnh từ Đá đến Đích: Có cạnh từ hòn đá i (thỏa mãn điều kiện hữu ích Y) đến đỉnh đích nếu hòn đá đó chạm vào hoặc vượt qua đường X=U. Điều này xảy ra nếu X_i + R_i >= U.
Bài toán tìm đường đi ngắn nhất: Ta cần tìm đường đi từ đỉnh nguồn đến đỉnh đích sử dụng ít đá nhất. Đây chính là bài toán tìm đường đi ngắn nhất trên đồ thị không trọng số (hoặc trọng số mỗi cạnh là 1).
Sử dụng BFS (Breadth-First Search):
- BFS là thuật toán hiệu quả để tìm đường đi ngắn nhất theo số lượng cạnh trong đồ thị không trọng số.
- Trạng thái: Trong BFS, trạng thái có thể là chỉ số của hòn đá hiện tại mà kiến đang đứng trên đó.
- Độ đo khoảng cách: Lưu trữ dist[i] là số hòn đá tối thiểu cần dùng để đi từ bờ X=0 đến hòn đá i.
- Khởi tạo:
  - Tạo một mảng dist kích thước N, khởi tạo tất cả giá trị là -1 (chưa thăm).
  - Tạo một queue cho BFS.
  - Với mỗi hòn đá i (0 đến N-1): Nếu nó hữu ích (theo Y) VÀ chạm bờ X=0 (X_i - R_i <= 0), thì đẩy i vào queue và gán dist[i] = 1 (vì cần 1 hòn đá để đến được đây từ bờ).
- Quá trình BFS:
  - Trong khi queue còn phần tử:
    - Lấy hòn đá u từ đầu queue.
    - Nếu hòn đá u chạm bờ X=U (X_u + R_u >= U), thì ta đã tìm được đường đi đến đích. Số đá cần dùng là dist[u]. Trả về dist[u] và kết thúc.
    - Duyệt qua tất cả các hòn đá khác v (0 đến N-1, v != u):
      - Nếu hòn đá v hữu ích (theo Y) VÀ chưa thăm (dist[v] == -1) VÀ hòn đá u giao với hòn đá v:
        
        Gán dist[v] = dist[u] + 1.
        
        Đẩy v vào queue.
- Kết quả: Nếu queue rỗng mà vẫn chưa tìm được đường đến đích (không trả về), nghĩa là không thể vượt sông. Trả về -1.
Lưu ý:
- Kiểm tra điều kiện hữu ích theo trục Y ([L, U]) là rất quan trọng để chỉ xem xét các hòn đá trong luồng sông.
- Sử dụng long long khi tính bình phương khoảng cách để tránh tràn số nếu tọa độ và bán kính đủ lớn (mặc dù với ràng buộc này thì int có thể đủ cho kết quả bình phương, nhưng long long an toàn hơn).
- Bài toán yêu cầu số hòn đá tối thiểu, BFS tính số cạnh (chuyển từ đá này sang đá khác hoặc từ bờ/đá đầu tiên đến đá). Cách gán dist[i]=1 ban đầu cho các đá chạm bờ X=0 đảm bảo dist[i] chính là số đá đã dùng.

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

Comments

There are no comments at the moment.