Bài tập lập trình tìm đường đi ngắn nháyt năm 2024

• Information
• AI Chat

Was this document helpful?

Was this document helpful?

3

2

9

6

Bài Tập

Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh Z bằng thuật toán Dijkstra

Bảng Kết Quả

k Đỉnh S Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh Z

k là số thứ tự, bắt đầu từ 0

Mỗi đỉnh là tiêu đề mỗi cột, thứ tự không quan trọng.

Bảng Kết Quả

k Đỉnh S Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh Z

0 (0, S)* (

, S)

Ở bước khởi tạo, ứng với k = 0,

Đỉnh xuất phát có độ dài đường đi từ đỉnh S đến S là 0, nên ta viết (0, S). Đỉnh 1 có độ dài đường đi ngắn

nhất từ đỉnh 5 đến 1 là

, S) .

Đánh dấu * vào đỉnh có đường đi từ đỉnh S đến nó là ngắn nhất.

Bảng Kết Quả

k Đỉnh S Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh Z

0 (0, S)* (

, S)

1 - (2, S)* (9, S) (7, S) (13, S) (

, S)

Tại k = 1, tỉnh lại độ dài đường đi ngắn nhất từ S đến các đỉnh kề với đỉnh S

L(1) = L(s) + w(s, 1)= 0 + 2 = 2 ⇒ (2, S)

• Home
• My Library
• Ask AI

Đây là bài viết số 2 trong series bài viết về Bài toán đường đi ngắn nhất trên đồ thị. Để theo dõi lại phần 1 của series, các bạn hãy nhấn vào đây.

I. Tổng quan

1. Phát biểu bài toán

Ta đã biết về thuật toán Floyd - Warshall trong bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trước đây. Thuật toán hoạt động rất hiệu quả trong các bài toán cần xác định nhanh đường đi ngắn nhất giữa hai đỉnh bất kì, tuy nhiên nhược điểm của nó là độ phức tạp khá lớn lên tới O(n3),O(n^3), vì vậy chỉ có thể sử dụng trên các đồ thị có số đỉnh vừa phải.

Trên thực tế, không phải lúc nào ta cũng cần tìm ra đường đi ngắn nhất giữa mọi cặp đỉnh. Bài toán đường đi ngắn nhất xuất phát từ một đỉnh (single-source shortest path) là một bài toán rất thông dụng như vậy, bài toán của giải thuật Floyd chỉ là dạng biến đổi của nó mà thôi. Bài toán này được phát biểu như sau:

Cho đơn đồ thị có hướng, có trọng số G=(V,E,w),G = (V, E, w), các đỉnh được đánh số từ 11 tới nn. Độ dài của đường đi ngắn nhất giữa hai đỉnh ss và tt được kí hiệu là d(s,t),d(s, t), và nếu như không tồn tại đường đi từ đỉnh ss tới một đỉnh tt nào đó thì ta sẽ coi d(s,t)=∞d(s, t) = \infty.

Yêu cầu: Hãy tìm các đường đi ngắn nhất từ một đỉnh xuất phát ss cho trước tới một đỉnh tt cho trước trên đồ thị?

Input:

Dòng đầu tiên chứa hai số nguyên dương nn và mm - số đỉnh và số cạnh của đồ thị. Dòng thứ hai chứa hai số nguyên dương ss và tt - hai đỉnh xuất phát và đỉnh đích cần tìm đường đi ngắn nhất. Trên mm dòng tiếp theo, mỗi dòng chứa ba số nguyên dương u,v,wu,vu, v, w_{u, v} - thể hiện một cung nối từ đỉnh uu tới đỉnh vv trên đồ thị có trọng số là wu,vw_{u, v}.

Ràng buộc:

1≤n,m≤1051 \le n, m \le 10^5. 1≤u≠v≤n1 \le u \ne v \le n. ∣wu,v∣≤105|w_{u, v}| \le 10^5.

Output:

Dòng thứ nhất in ra độ dài đường đi ngắn nhất giữa hai đỉnh ss và tt. Nếu không tồn tại đường đi thì in ra −1-1. Dòng thứ hai in ra các đỉnh trên đường đi ngắn nhất từ ss tới tt nếu tồn tại, các đỉnh phân tách nhau bởi dấu cách.

Sample Input:

6 7 1 4 1 2 1 1 6 20 2 3 2 3 6 3 3 4 20 5 4 5 6 5 4

Sample Output:

15 1 2 3 6 5 4

Bài toán trên thực tế sẽ phải quy về việc tìm đường đi ngắn nhất từ đỉnh ss tới tất cả các đỉnh còn lại. Trong bài viết này, tôi sẽ giới thiệu tới các bạn một số thuật toán thông dụng để giải bài toán này, đó là Dijkstra và Ford Bellman. Ta quy ước các giải thuật sẽ được cài đặt trên đơn đồ thị có hướng. Trong trường hợp đồ thị là vô hướng ta vẫn quy được về đồ thị có hướng bằng cách coi mỗi cạnh là hai cung ngược chiều nhau.

2. Cấu trúc bài toán con tối ưu

Các thuật toán tìm đường đi ngắn nhất mà chúng ta sẽ khảo sát trong bài viết này đều dựa trên một đặc tính chung: Mỗi đoạn đường trên đường đi ngắn nhất phải là một đường đi ngắn nhất.

Ta có định lý sau:

Định lý 1.1: Cho đồ thị có trọng số G=(V,E,w),G = (V, E, w), gọi P={v1,v2,…,vk}P = \{v_1, v_2, \dots, v_k\} là một đường đi ngắn nhất từ v1v_1 tới vkv_k. Khi đó ∀i,j:1≤i≤j≤k,\forall i, j: 1 \le i \le j \le k, đoạn đường Pij={vi,vi+1,…,vj}P_{ij} = \{v_i, v_{i + 1}, \dots, v_j\} là một đường đi ngắn nhất từ viv_i tới vjv_j.

Bởi tính chất bài toán con tối ưu nói trên, hầu hết các thuật toán tìm đường đi ngắn nhất đều là thuật toán Quy hoạch động (ví dụ như Floyd) hoặc Tham lam (ví dụ như Dijkstra).

Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào. Trong trường hợp như vậy, bài toán có thể quy về tìm đường đi đơn ngắn nhất, tuy nhiên hiện nay vẫn chưa ai tìm được một thuật toán tìm đường đi đơn ngắn nhất trên đồ thị có chu trình âm. Vì vậy, trong phạm vi bài viết này, ta sẽ xét các thuật toán tìm đường đi ngắn nhất trên đồ thị không có chu trình âm.

II. Thuật toán Ford Bellman - Đồ thị không có chu trình âm

1. Ý tưởng

Trên đơn đồ thị có hướng không có chu trình âm, thuật toán Ford Bellman có ý tưởng rất đơn giản như sau: Với đỉnh xuất phát s,s, gọi d[v]d[v] là độ dài đường đi ngắn nhất từ ss tới vv. Ban đầu ta khởi tạo:

• d[s]=0d[s] = 0.
• d[v]=+∞;∀v≠sd[v] = +\infty; \forall v \ne s.

Các d[v]d[v] sẽ lần lượt được tối ưu hóa như sau: Xét mọi cặp đỉnh u,vu, v của đồ thị, nếu như có một cặp đỉnh mà d[v]>d[u]+wu,vd[v] > d[u] + w_{u, v} và d[u]≠+∞d[u] \ne +\infty thì ta gán lại:

d[v]=d[u]+wu,vd[v] = d[u] + w_{u, v}

Tức là, nếu độ dài đường đi từ ss tới vv hiện tại bị lớn hơn độ dài đường đi từ ss tới uu cộng với trọng số đi từ uu tới vv thì ta sẽ hủy bỏ đường đi cũ và coi đường đi mới từ ss tới vv chính là đường đi từ ss tới uu rồi từ uu tới vv. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kì một giá trị d[v]d[v] nào nữa.

fill(d + 1, d + n + 1, inf);
bool stop = false;
while (!stop)
{
    stop = true;
    for (int u = 1; u <= n; ++u)
        for (int v kề u)
            if (d[v] > d[u] + w(u, v))
            {
                d[v] = d[u] + w(u, v);
                stop = false;
            }
}

Chứng minh: Tại bước khởi tạo, mỗi d[v]d[v] chính là độ dài ngắn nhất của đường đi từ ss tới vv đi qua không quá 00 cạnh.

Giả sử tại bước lặp thứ i (i≥1),d[v]i \ (i≥1), d[v] đã bằng độ dài ngắn nhất đi từ ss tới vv qua không quá i−1i - 1 cạnh. Đường đi từ ss tới vv qua không quá ii cạnh sẽ được thành lập bằng cách: Lấy một đường đi từ ss tới một đỉnh uu nào đó kề với ss (qua không quá i−1i - 1 cạnh), rồi đi tiếp tới vv bằng cung trực tiếp (u→v),(u \to v), do đó đường đi ngắn nhất từ ss tới vv qua không quá ii cạnh sẽ được tính bằng giá trị nhỏ nhất trong hai giá trị dưới đây (nguyên lí tối ưu Bellman):

Độ dài đường đi ngắn nhất từ ss tới vv qua không quá i−1i - 1 cạnh (ở bước trước). Độ dài đường đi ngắn nhất từ ss tới uu (qua không quá i−1i - 1 cạnh) cộng với trọng số cung (u→v)(u \to v).

Vì vậy, sau mỗi bước lặp, d[v]d[v] được tối ưu bằng công thức:

d[v]bước i=min(d[v]bước i−1,d[u]bước i−1+wu,v)d[v]_{\text{bước } i} = \text{min} \big( d[v]_{\text{bước }i - 1}, d[u]_{\text{bước } i - 1} + w_{u, v} \big)

Sau bước lặp thứ n−1,n - 1, ta có d[v]d[v] bằng độ dài đường đi ngắn nhất từ ss tới vv qua không quá n−1n - 1 cạnh. Vì đồ thị không có chu trình âm, do đó sẽ có một đường đi ngắn nhất từ ss tới vv là đường đi cơ bản (đi qua không quá n−1n - 1 cạnh, do đường đi cơ bản là đường đi không có đỉnh lặp lại, mà đồ thị có nn đỉnh thì cần đi qua tối đa n−1n - 1 cạnh để đạt được đường đi cơ bản). Tức là d[v]d[v] sẽ là độ dài đường đi ngắn nhất từ ss tới v,v, hay nói cách khác, số bước lặp để tối ưu hóa sẽ không vượt quá n−1n - 1 bước.

Muốn truy vết lại đường đi ngắn nhất, ta sử dụng mảng trace[v]trace[v] để lưu lại đỉnh liền trước vv trong đường đi ngắn nhất từ ss tới vv. Mỗi khi cập nhật lại một d[v]=d[u]+wu,vd[v] = d[u] + w_{u, v} thì đồng thời cập nhật lại đỉnh liền trước vv trên đường đi tối ưu sẽ là u,u, và gán luôn:

trace[v]=utrace[v] = u

Thuật toán cũng có thể được cải tiến để xác định được đồ thị có tồn tại chu trình âm hay không theo ý tưởng sau:

• Sau khi xác định xong mọi d[v],d[v], xét lại các cung (u→v)(u \to v) của đồ thị.
• Nếu như vẫn tồn tại một cung khiến cho d[v]d[v] nào đó có thể tối ưu hóa hơn nữa (d[v]>d[u]+wu,v)(d[v] > d[u] + w_{u, v}) thì đồ thị sẽ có chu trình âm. Khi đó kết luận không thể tồn tại đường đi ngắn nhất từ ss tới tt.

2. Cài đặt

Danh sách cạnh là phương pháp tốt nhất để biểu diễn đồ thị trong thuật toán Ford Bellman.

Giá trị +∞+\infty sẽ được gán bằng một hằng số thật lớn trong khi lập trình, ở đây tác giả lựa chọn giá trị 101810^{18}.

# include 

# define int long long
using namespace std;
const int inf = 1e18;
struct edge
{
    int u, v, w;
};
bool check_negative_cycle(int m, vector < edge > &edges_list, vector < int > &d)
{
    // Nếu vẫn tồn tại cung (u -> v) mà d[v] có thể tối ưu hóa được thêm thì
    // đồ thị sẽ tồn tại chu trình âm, trả về true cho hàm.
    for (int i = 1; i <= m; ++i)
    {
        int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
        if (d[u] != inf && d[u] + w < d[v])
            return true;
    }
    return false;
}
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
    cout << d[t] << '\n';
    vector < int > path;
    while (t != s)
    {
        path.push_back(t);
        t = trace[t];
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    for (int u: path)
        cout << u << ' ';
}
void bellman_ford(int n, int m, int s, int t, vector < edge > &edges_list)
{
    vector < int > d(n + 1, inf);
    vector < int > trace(n + 1);
    d[s] = 0;
    // Lặp tối đa n - 1 lần.
    for (int step = 1; step <= n - 1; ++step)
    {
        bool stop = true;
        for (int i = 1; i <= m; ++i)
        {
            int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
            if (d[u] != inf && d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                trace[v] = u;
                stop = false;
            }
        }
        // Nếu không thể tối ưu d[v] nào nữa thì dừng thuật toán.
        if (stop) break;
    }
    // Nếu đồ thị có chu trình âm hoặc d[t] = oo thì không tìm được đường đi.
    // Ngược lại truy vết đường đi từ s tới t.
    if (check_negative_cycle(m, edges_list, d) || d[t] == inf)
        cout << -1;
    else
        print_result(s, t, d, trace);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector < edge > edges_list(m + 1);
    for (int i = 1; i <= m; ++i)
        cin >> edges_list[i].u >> edges_list[i].v >> edges_list[i].w;
    bellman_ford(n, m, s, t, edges_list);
    return 0;
}

Trong trường hợp đề bài yêu cầu tìm ra một chu trình âm gặp phải trên đường đi từ s,s, ta có thể thực hiện thêm một số bước dưới đây:

• Bước 1: Tìm ra đỉnh xx mà d[x]d[x] vẫn còn có thể tối ưu thêm sau khi đã thực hiện giải thuật Ford Bellman n−1n - 1 lần. Đây chính là một đỉnh nằm trong chu trình âm.
• Bước 2: Tìm ra đỉnh đầu tiên thuộc chu trình âm mà từ ss tới được nó, bằng cách đi ngược lại x=trace[x]x = trace[x] đủ nn lần.
• Bước 3: Từ đỉnh x,x, tìm ra các đỉnh thuộc chu trình âm chứa xx bằng cách liên tục ghi nhận xx rồi đi ngược về trace[x]trace[x] tới khi quay lại đỉnh xx ở bước 22 tìm được.

Đoạn chương trình kiểm tra chu trình âm có thể điều chỉnh như sau để thu được các đỉnh thuộc chu trình âm:

void check_negative_cycle(int m, vector < edge > &edges_list, vector < int > &d, 
                                    vector < int > &trace)
{
    int x = -1;
    for (int i = 1; i <= m; ++i)
    {
        int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
        if (d[u] != inf && d[u] + w < d[v])
        {
            d[v] = d[u] + w;
            trace[v] = u;
            x = v;
        }
    }
    // Tìm thấy chu trình âm.
    if (x != -1)
    {
        // Tìm đỉnh xuất phát của chu trình âm, tức là đỉnh đầu tiên 
        // thuộc chu trình âm mà từ s tới đuợc nó.
        for (int i = 1; i <= n; ++i)
            x = trace[x];
        // Tìm ra các đỉnh thuộc chu trình âm. 
        vector < int > negative_cycle;
        for (int y = x; ; y = trace[y])
        {
            negative_cycle.push_back(y);
            if (y == x && negative_cycle.size() > 1)
                break;
        }
        reverse(negative_cycle.begin(), negative_cycle.end());
        // In chu trình âm.
        for (int u: negative_cycle)
            cout << u << ' ';
    }
}

3. Đánh giá

Về mặt bộ nhớ, do sử dụng danh sách cạnh để biểu diễn đồ thị nên độ phức tạp bộ nhớ của thuật toán là O(∣E∣)O\big(|E|\big).

Về mặt thời gian, dễ thấy thuật toán lặp không quá n−1n - 1 lần, và mỗi lần phải lặp qua cả mm cạnh để tối ưu các d[v]d[v]. Vì thế độ phức tạp tính toán tổng quát là O(∣V∣.∣E∣)O\big(|V|.|E|\big).

III. Thuật toán Dijkstra - Đồ thị có trọng số trên các cung không âm

1. Giải thuật cơ bản

Ý tưởng

Trong trường hợp đồ thị có trọng số trên các cung không âm, thuật toán Dijkstra là một thuật toán hoạt động hiệu quả hơn rất nhiều so với Ford Bellman. Thuật toán Ford Bellman mặc dù giải quyết được bài toán trong trường hợp tổng quát, nhưng tồn đọng sự bất tiện sau đây:

Với mỗi đỉnh v,v, đặt d[v]d[v] là độ dài đường đi ngắn nhất từ ss tới vv. Thuật toán Ford Bellman khởi tạo d[s]=0d[s] = 0 và d[v]=+∞;∀v:v≠s;d[v] = +\infty; \forall v: v \ne s; rồi tối ưu hóa dần các giá trị d[v]d[v] theo công thức: d[v]=min(d[v],d[u]+wu,v)d[v] = \text{min}\big(d[v], d[u] + w_{u, v}\big). Như vậy, nếu ta dùng một đỉnh uu để tối ưu hóa đỉnh v,v, và sau đó ở một bước nào đấy d[u]d[u] lại được tối ưu thêm, thì mọi d[v]d[v] liên quan tới d[u]d[u] ở bước trước đó đều sẽ phải sửa lại, dẫn tới việc sửa đi sửa lại nhiều lần.

Thuật toán Dijkstra có ý tưởng là thay vì duyệt lại mọi cung (u→v)(u \to v) để tối ưu hóa d[v],d[v], ta sẽ chọn ngay một đỉnh uu mà d[u]d[u] không thể tối ưu thêm nữa rồi dùng nó để tối ưu hóa các đỉnh vv kề với nó. Đỉnh uu được chọn này sẽ là đỉnh uu có d[u]d[u] nhỏ nhất hiện tại. Như vậy, thuật toán có thể mô tả như sau:

• Bước 1: Khởi tạo Với đỉnh v,v, gọi d[v]d[v] là độ dài đường đi ngắn nhất từ ss tới vv. Ban đầu khởi gán d[s]=0d[s] = 0 và d[v]=+∞;∀v:v≠sd[v] = +\infty; \forall v: v \ne s. Mỗi đỉnh sẽ có hai trạng thái: Còn có thể tối ưu tiếp hoặc không thể tối ưu hơn, được thể hiện bởi mảng is_free[u]=TRUE\text{is\_free}[u] = \text{TRUE} hoặc is_free[u]=FALSE\text{is\_free}[u] = \text{FALSE} tùy theo uu còn có thể tối ưu tiếp hoặc không. Ban đầu ta có is_free[u]=TRUE;∀u:1≤u≤n\text{is\_free}[u] = \text{TRUE}; \forall u: 1 \le u \le n.
• Bước 2: Lặp và tính toán Bước này gồm hai thao tác được liên tục lặp lại tới khi đỉnh đích tt được cố định, hoặc tất cả các đỉnh uu còn có thể tối ưu tiếp lại đều có d[u]=+∞d[u] = +\infty (tức là không tồn tại đường đi):
  • Cố định nhãn: Chọn trong các đỉnh còn có thể tối ưu tiếp, lấy ra đỉnh uu có d[u]d[u] nhỏ nhất, rồi đánh dấu nó là không thể tối ưu hơn được nữa.
  • Sửa nhãn: Dùng đỉnh uu vừa lấy ra, xét tất cả đỉnh vv kề với nó và sửa lại giá trị d[v]d[v] theo công thức: d[v]=min(d[v],d[u]+wu,v)d[v] = \text{min}\big(d[v], d[u] + w_{u, v}\big)
• Bước 3: In kết quả Kết hợp với việc lưu vết đường đi trong quá trình cập nhật các d[u],d[u], thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (nếu d[t]=+∞d[t] = +\infty).

  Chứng minh:

Tại sao ở mỗi bước lặp, đỉnh uu với d[u]d[u] nhỏ nhất lại được chọn để cố định và tối ưu các đỉnh xung quanh nó?

Ta sử dụng phương pháp phản chứng: Giả sử đỉnh uu như vậy vẫn còn có thể tối ưu thêm, thì phải tồn tại một đỉnh u1u_1 nào đó với is_free[u1]=TRUE\text{is\_free}[u_1] = \text{TRUE} sao cho d[u]>d[u1]+wu1,ud[u] > d[u_1] + w_{u_1, u}. Do trọng số wu1,uw_{u_1, u} không âm nên chắc chắn d[u1]>d[u],d[u_1] > d[u], điều này trái với cách chọn d[u]d[u] là nhỏ nhất lúc đầu.

Vậy đỉnh uu với d[u]d[u] nhỏ nhất tất nhiên phải là đỉnh không thể tối ưu được thêm nữa.

Việc truy vết có thể thực hiện tương tự như trong giải thuật Ford Bellman, với trace[v]trace[v] là đỉnh liền trước vv trên đường đi ngắn nhất từ ss tới vv. Mỗi khi cập nhật một giá trị d[v]=d[u]+wu,vd[v] = d[u] + w_{u, v} thì đồng thời cập nhật luôn trace[v]=utrace[v] = u.

Cài đặt

# include 

# define int long long
using namespace std;
const int maxn = 1e5 + 1, inf = 1e18;
vector < pair < int, int > > adj[maxn];
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
    if (d[t] == inf)
        cout << -1;
    else 
    {
        cout << d[t] << '\n';
        vector < int > path;
        while (t != s)
        {
            path.push_back(t);
            t = trace[t];
        }
        path.push_back(s);
        reverse(path.begin(), path.end());
        for (int v: path)
            cout << v << ' ';
    }
}
void dijkstra(int n, int m, int s, int t)
{
    vector < int > d(n + 1, inf);
    vector < bool > is_free(n + 1, true);
    vector < int > trace(n + 1);
    d[s] = 0;
    while (true)
    {
        int u = 0;
        for (int v = 1; v <= n; ++v)
            if (d[v] < d[u])
                u = v;
        if (u == 0)
            break;
        for (auto e: adj[u])
        {
            int v = e.first, w = e.second;
            if (is_free[v] && d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                trace[v] = u;
            }
        }
    }
    print_result(s, t, d, trace);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    dijkstra(n, m, s, t);
    return 0;
}

Đánh giá

Độ phức tạp bộ nhớ khi sử dụng danh sách kề để biểu diễn đồ thị sẽ là O(n+m)O(n + m).

Trong trường hợp xấu nhất, thuật toán đơn giản này sẽ cần nn lần cố định các d[v]d[v] và mất thêm O(n)O(n) để tìm đỉnh ra đỉnh uu có d[u]d[u] nhỏ nhất. Vì thế thuật toán có độ phức tạp tính toán tổng quát là là O(n2)O(n^2).

2. Cải tiến với cấu trúc Heap

Ý tưởng

Với những đồ thị có khoảng trên 1000010000 đỉnh, giải thuật ở trên sẽ không thể đáp ứng được yêu cầu về thời gian thực thi. Giải pháp là cải tiến việc tìm ra đỉnh uu có d[u]d[u] nhỏ nhất, thông qua cấu trúc dữ liệu Heap (mà trong C++ đã cài đặt sẵn dưới dạng hàng đợi ưu tiên -

15
1 2 3 6 5 4

3):

• Khởi tạo một hàng đợi ưu tiên dạng

  15 1 2 3 6 5 4

  4, trong đó mỗi phần tử sẽ lưu một đỉnh vv vẫn còn có thể tối ưu tiếp kèm theo giá trị d[v]d[v] hiện tại của nó.
• Phần tử với d[v]d[v] nhỏ nhất sẽ được đưa lên đầu hàng đợi. Ban đầu trong hàng đợi ưu tiên chỉ có phần tử (d[s],s)(d[s], s) (đỉnh xuất phát cùng với nhãn bằng 00 của nó).

Thuật toán diễn ra thông qua các bước lặp trên hàng đợi ưu tiên cho tới khi hàng đợi rỗng, hoặc phần tử chứa d[t]d[t] được đưa lên đầu hàng đợi (tức là đường đi tới đỉnh tt đã được tối ưu):

• Bước 1: Lấy ra đỉnh uu ở đầu hàng đợi, đỉnh này chính là đỉnh có d[u]d[u] không thể tối ưu được nữa (và là nhỏ nhất). Đánh dấu nó là không thể tối ưu được nữa (gán is_free[u]=FALSE\text{is\_free}[u] = \text{FALSE}) rồi xóa khỏi hàng đợi ưu tiên.
• Bước 2: Sử dụng đỉnh u,u, tối ưu các đỉnh vv kề với nó mà có is_free[v]=TRUE\text{is\_free}[v] = \text{TRUE} theo công thức: d[v]=min(d[v],d[u]+wu,v);d[v] = \text{min}\big(d[v], d[u] + w_{u, v}\big); sau đó đưa phần tử (d[v],v)(d[v], v) vào hàng đợi ưu tiên.

Cài đặt

# include 

# define int long long
using namespace std;
typedef pair < int, int > pi;
const int maxn = 1e5 + 1, inf = 1e18;
vector < pair < int, int > > adj[maxn];
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
    if (d[t] == inf)
        cout << -1;
    else 
    {
        cout << d[t] << '\n';
        vector < int > path;
        while (t != s)
        {
            path.push_back(t);
            t = trace[t];
        }
        path.push_back(s);
        reverse(path.begin(), path.end());
        for (int v: path)
            cout << v << ' ';
    }
}
void dijkstra_heap(int n, int m, int s, int t)
{
    vector < int > d(n + 1, inf);
    vector < bool > is_free(n + 1, true);
    vector < int > trace(n + 1);
    priority_queue < pi, vector < pi >, greater < pi > > qu_min;
    d[s] = 0;
    qu_min.push({d[s], s});
    while (!qu_min.empty())
    {
        int u = qu_min.top().second;
        int du = qu_min.top().first;
        qu_min.pop();
        if (u == t)
            break;
        is_free[u] = false;
        for (auto e: adj[u])
        {
            int v = e.first, w = e.second;
            if (is_free[v] && d[v] > du + w)
            {
                d[v] = du + w;
                trace[v] = u;
                qu_min.push({d[v], v});
            }
        }
    }
    print_result(s, t, d, trace);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    dijkstra_heap(n, m, s, t);
    return 0;
}

Đánh giá

Với việc sử dụng danh sách kề, độ phức tạp về bộ nhớ của thuật toán chỉ là O(∣V∣+∣E∣)O\big(|V| + |E|\big).

Về độ phức tạp tính toán, do việc áp dụng

15
1 2 3 6 5 4

3 để tìm ra đỉnh uu tốt nhất ở mỗi bước, nên độ phức tạp tổng quát của thuật toán là O(max(∣V∣,∣E∣).log⁡(∣V∣))O\Big(\text{max}\big(|V|, |E|\big).\log\big(|V|\big)\Big).

IV. Bài tập áp dụng

1. Cai trị vương quốc

Đề bài (Tóm tắt)

Nhà vua của một vương quốc nọ là người không thông minh cho lắm, ông ta chỉ có thể làm được các phép tính cộng, so sánh lớn hơn (

15
1 2 3 6 5 4

6. và nhỏ hơn (

15
1 2 3 6 5 4

7. với một số nguyên cho trước, cũng như tính tổng một dãy con liên tiếp trong một dãy số cho trước. Vì vậy, các vấn đề khi trình lên nhà vua để nhận quyết định đều được mô tả bằng một dãy số nguyên, sau đó nhà vua sẽ đưa ra quyết định bằng cách ra thông báo rằng tổng của dãy số đó lớn hơn hay nhỏ hơn một số nguyên nào đó.

Ngày nọ, một nhóm những kẻ chống đối trình lên nhà vua một vấn đề lớn dưới dạng một dãy số nguyên S={a1,a2,…,an};S = \{a_1, a_2, \dots, a_n\}; sau đó xin quyết định của nhà vua cho mm vấn đề nhỏ dưới dạng một dãy con S_i = \{a_{s_i}, a_{s_i + 1}, \dots, a_{s_i + n_i\} \ (1 \le i \le m) thuộc dãy SS. Nhà vua đã đưa ra quyết định nhanh chóng: Với mỗi dãy con Si,S_i, ngài đưa ra một số nguyên kik_i rồi thông báo tổng của dãy con SiS_i lớn hơn hoặc nhỏ hơn kik_i - đó chính là quyết định của ngài. Rồi như thường lệ, nhà vua lãng quên dãy số SS ban đầu đã nhận được.

Tuy nhiên, nhà vua đã rơi vào âm mưu của những kẻ chống đối! Chúng đã tìm ra những sai sót trong quyết định của nhà vua và vin vào đó để tổ chức những cuộc biểu tình, hòng bắt ép nhà vua thoái vị. Nhận được tin báo, nhà vua rất lo lắng vì ngài đã quên mất dãy số SS ban đầu mình nhận được. Vì vậy, nhà vua quyết định đưa ra một dãy SS giả mạo sao cho nó thỏa mãn tất cả các quyết định mà ngài đã đưa ra, rồi tuyên bố rằng đó chính là vấn đề ban đầu mà mình nhận được.

Yêu cầu: Hãy xác định xem nhà vua có thể tìm ra dãy SS giả mạo thỏa mãn tất cả những quyết định mà ngài đã đưa ra hay không?

Input:

• Gồm nhiều test cases, mỗi test case gồm một nhóm dòng có cấu trúc như sau:
  • Dòng đầu tiên chứa hai số nguyên dương n,mn, m - độ dài của dãy SS nhà vua nhận được và số lượng quyết định nhà vua đã đưa ra.
  • Trên mm dòng tiếp theo, mỗi dòng chứa một bộ bốn giá trị si,ni,oi,kis_i, n_i, o_i, k_i - với oio_i là

    15 1 2 3 6 5 4

    8 thể hiện cho phép so sánh

    15 1 2 3 6 5 4

    6 hoặc

    fill(d + 1, d + n + 1, inf); bool stop = false; while (!stop) {

       stop = true;  
       for (int u = 1; u <= n; ++u)  
           for (int v kề u)  
               if (d[v] > d[u] + w(u, v))  
               {  
                   d[v] = d[u] + w(u, v);  
                   stop = false;  
               }  
    

    }

    0 thể hiện cho phép so sánh

    15 1 2 3 6 5 4

    7. Đây là một quyết định của nhà vua cho biết dãy con si={asi,asi+1,…,asi+ni}s_i = \{a_{s_i}, a_{s_i + 1}, \dots, a_{s_i + n_i}\} có tổng lớn hơn hoặc nhỏ hơn giá trị kik_i theo thể hiện của oio_i.
• Dòng cuối cùng của đầu vào chứa duy nhất số 00 - thể hiện kết thúc việc nhập dữ liệu.

Ràng buộc:

• 1≤n≤1001 \le n \le 100.
• 1≤m≤1001 \le m \le 100.

Output:

• Ứng với mỗi test case, in ra

  fill(d + 1, d + n + 1, inf); bool stop = false; while (!stop) {

  stop = true;  
  for (int u = 1; u <= n; ++u)  
      for (int v kề u)  
          if (d[v] > d[u] + w(u, v))  
          {  
              d[v] = d[u] + w(u, v);  
              stop = false;  
          }  
  

  }

  2 nếu như nhà vua không thể tìm ra một dãy SS giả mạo phù hợp, ngược lại in ra

  fill(d + 1, d + n + 1, inf); bool stop = false; while (!stop) {

  stop = true;  
  for (int u = 1; u <= n; ++u)  
      for (int v kề u)  
          if (d[v] > d[u] + w(u, v))  
          {  
              d[v] = d[u] + w(u, v);  
              stop = false;  
          }  
  

  }
  3. Kết quả của mỗi test case được in ra trên một dòng.

Sample Input:

4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0 
0

Sample Output:

lamentable kingdom
successful conspiracy

Ý tưởng

Cai Trị Vương Quốc - Editorial

Xét hàm sum(k)=∑i=1kaisum(k) = \sum_{i = 1}^k a_i và coi sum(0)=0sum(0) = 0.

Gọi tổng của dãy con si={asi,asi+1,…,asi+ni}s_i = \{a_{s_i}, a_{s_i + 1}, \dots, a_{s_i + n_i}\} là sumi (1≤i≤m)sum_i \ (1 \le i \le m). Từ tính chất tổng tiền tố, ta biết rằng sumi=sum(si+ni)−sum(si−1)sum_i = sum(s_i + n_i) - sum(s_i - 1). Khi đó, quyết định thứ i (1≤i≤m)i \ (1 \le i \le m) của nhà vua sẽ tương ứng với:

sum(si+ni)−sum(si−1)>ki hoặc sum(si+ni)−sum(si−1) k_i \text{ hoặc } sum(s_i + n_i) - sum(s_i - 1) < k_i \ (*)

Như vậy, một dãy số S={a1,a2,…,an}S = \{a_1, a_2, \dots, a_n\} thỏa mãn tất cả các quyết định của nhà vua sẽ tồn tại khi và chỉ khi tồn tại một dãy các giá trị {sum(1),sum(2),…,sum(n)}\big\{sum(1), sum(2), \dots, sum(n)\big\} thỏa mãn điều kiện (∗)(*) với mọi i=1...mi = 1...m.

Ta lại biến đổi một chút ở các điều kiện:

• Với điều kiện aba > b tương đương với a≥b+1⇔−a≤−b−1a \ge b + 1 \Leftrightarrow -a \le -b - 1.

Áp dụng biến đổi trên vào dãy điều kiện (∗)(*) với mọi i=1...m,i = 1...m, ta có một dãy các ràng buộc ở dạng:

{sum(xi)−sum(yi)≤cixi,yi,ci∈N0≤xi,yi≤n\begin{cases}sum(x_i) - sum(y_i) \le c_i \\ x_i, y_i, c_i \in \mathbb{N} \\ 0 \le x_i, y_i \le n \end{cases}