+10

Bài toán đường đi ngắn nhất (phần 2) - Thuật toán Dijkstra và Ford Bellman

Đâ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 sstt đượ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 nnmm - số đỉnh và số cạnh của đồ thị.
  • Dòng thứ hai chứa hai số nguyên dương sstt - 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:

  • 1n,m1051 \le n, m \le 10^5.
  • 1uvn1 \le u \ne v \le n.
  • wu,v105|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 sstt. 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:1ijk,\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]=+;vsd[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}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 (i1),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á i1i - 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á i1i - 1 cạnh), rồi đi tiếp tới vv bằng cung trực tiếp (uv),(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á i1i - 1 cạnh (ở bước trước).
  • Độ dài đường đi ngắn nhất từ ss tới uu (qua không quá i1i - 1 cạnh) cộng với trọng số cung (uv)(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 i1,d[u]bước i1+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ứ n1,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á n1n - 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á n1n - 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 n1n - 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á n1n - 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 (uv)(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 <bits/stdc++.h>
#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 xxd[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 n1n - 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á n1n - 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] = 0d[v]=+;v:vs;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 (uv)(u \to v) để tối ưu hóa d[v],d[v], ta sẽ chọn ngay một đỉnh uud[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 uud[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] = 0d[v]=+;v:vsd[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:1un\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 uud[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 <bits/stdc++.h>
#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 uud[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 uud[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 - priority_queue):

  • Khởi tạo một hàng đợi ưu tiên dạng pair < int, int >, 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 <bits/stdc++.h>
#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 priority_queue để 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 (>) và nhỏ hơn (<) 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_igt thể hiện cho phép so sánh > hoặc lt thể hiện cho phép so sánh <. Đâ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:

  • 1n1001 \le n \le 100.
  • 1m1001 \le m \le 100.

Output:

  • Ứng với mỗi test case, in ra successful conspiracy 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 lamentable kingdom. 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}\}sumi (1im)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(si1)sum_i = sum(s_i + n_i) - sum(s_i - 1). Khi đó, quyết định thứ i (1im)i \ (1 \le i \le m) của nhà vua sẽ tương ứng với:

sum(si+ni)sum(si1)>ki hoặc sum(si+ni)sum(si1)<ki ()sum(s_i + n_i) - sum(s_i - 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 a<b,a < b, nó tương đương với ab1a \le b - 1 và tương tự, a>ba > b tương đương với ab+1ab1a \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,ciN0xi,yin\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}

    Cụ thể hơn, nếu như sum(xi)sum(yi)>kisum(x_i) - sum(y_i) > k_i thì ta đưa nó về sum(yi)sum(xi)ki1;sum(y_i) - sum(x_i) \le -k_i - 1; ngược lại thì đưa về sum(xi)sum(yi)ki1sum(x_i) - sum(y_i) \le k_i - 1. Ở đây xi=si1x_i = s_i - 1yi=si+niy_i = s_i + n_i.

Dãy các ràng buộc như trên được gọi là "Hệ thống các ràng buộc khác nhau (System of difference constraints)" - một mô hình toán học sử dụng rất rộng rãi trong khoa học máy tính, và được giải quyết thông qua phương pháp xây dựng "Đồ thị ràng buộc". Trên đồ thị này, các đỉnh được đánh số từ 00 tới n,n, và mỗi điều kiện được thể hiện bởi một cung nối từ đỉnh yiy_i tới đỉnh xix_i trên đồ thị (hoặc ngược lại) với trọng số là cic_i. Riêng đỉnh 00 (đỉnh đặc biệt) sẽ có cung nối tới tất cả các đỉnh còn lại với trọng số là 00.

Sau khi xây dựng đồ thị, nếu như đồ thị không có chu trình âm và tất cả các cic_i đều là số nguyên thì sẽ tồn tại một đáp án số nguyên phù hợp với tất cả các ràng buộc, ngược lại thì không có đáp án nào cả (tức là không tồn tại dãy số SS thỏa mãn).

Ta có thể sử dụng thuật toán Ford Bellman để giải quyết bài toán trên. Tuy nhiên, đỉnh đặc biệt trong bài toán này sẽ được chọn là đỉnh n+1n + 1 do đỉnh 00 vẫn tồn tại trong đồ thị ban đầu.

Độ phức tạp: O(n×m)O(n \times m).

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int inf = LLONG_MAX;

struct edge
{
    int u, v, w;
};

// Xác định chu trình âm trên đồ thị.
bool check_negative_cycle(vector < edge > &edges, vector < int > &d)
{
    for (int i = 1; i < edges.size(); ++i)
    {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (d[u] != inf && d[u] + w < d[v])
            return true;
    }

    return false;
}

// Thuật toán Ford Bellman xuất phát từ 1 đỉnh.
void solution(int n, int source, vector < edge > &edges)
{
    vector < int > d(n + 1, inf);
    d[source] = 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 < edges.size(); ++i)
        {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            if (d[u] != inf && d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                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;
    }

    if (check_negative_cycle(edges, d))
        cout << "successful conspiracy\n";
    else
        cout << "lamentable kingdom\n";

}

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

    while (true)
    {
        int n, m;
        cin >> n;

        if (n == 0)
            break;

        cin >> m;

        vector < edge > edges(m + 1);
        for (int i = 1; i <= m; ++i)
        {
            int si, ni, ki;
            string oi;
            cin >> si >> ni >> oi >> ki;

            int u, v, w;
            // Trường hợp s(x) - s(y) > k <=> s(y) - s(x) <= -k - 1.
            if (oi == "gt")
            {
                u = si + ni;
                v = si - 1;
                w = -ki - 1;
            }
            else // Trường hợp s(x) - s(y) < k <=> s(x) - s(y) <= k - 1.
            {
                u = si - 1;
                v = si + ni;
                w = ki - 1;
            }
            edges[i] = {u, v, w};
        }
        for (int u = 1; u <= n; ++u)
            edges.push_back({n + 1, u, 0});

        // Thực hiện Ford Bellman trên đồ thị gồm n + 2 đỉnh, đỉnh đặc biệt là n + 1.
        // Ford Bellman sẽ xuất phát từ đỉnh đặc biệt để đi tìm chu trình âm.
        solution(n + 2, n + 1, edges);
    }

    return 0;
}

2. Giao thông

Đề bài

Một mạng lưới giao thông bao gồm nn nút giao thông được đánh số từ 11 tới nnmm đoạn đường nối hai chiều giữa một số cặp nút. Trên mỗi đoạn đường, các xe đi qua chỉ được phép giới hạn trọng tải trong khoảng nhất định. Anh Long điều khiển một chiếc xe tải chở hàng từ nút giao thông 11 tới nút giao thông n,n, biết rằng nếu chở được càng nhiều hàng thì anh sẽ càng thu về nhiều lợi nhuận.

Yêu cầu: Hãy giúp anh Long tìm một hành trình đi từ nút 11 tới nút nn sao cho tải trọng xe cho phép trên hành trình đó là lớn nhất? Biết rằng, tải trọng xe cho phép trên hành trình là tải trọng xe cho phép nhỏ nhất trên một đoạn đường của hành trình đó.

Input:

  • Dòng đầu tiên chứa hai số nguyên dương n,mn,m.
  • Trên mm dòng tiếp theo, mỗi dòng gồm ba số nguyên dương u,v,wu,v,w cho biết có con đường hai chiều với giới hạn tải trọng là ww nối giữa hai vùng uuv (1u,vn)v \ (1≤u,v≤n).

Ràng buộc:

  • 2n1052≤ n ≤ 10^5.
  • 1m2×1051≤ m ≤2×10^5.
  • 1w1041≤ w ≤ 10^4.

Output:

  • Dòng thứ nhất ghi một số nguyên ww là tải trọng lớn nhất trên hành trình tìm được.
  • Dòng thứ hai ghi ra các nút giao thông trên hành trình tìm được, các số phân tách nhau

Sample Input:

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

Sample Output:

4
1 2 3 4 5 6

Ý tưởng

Bài toán có thể đưa về đồ thị với các đỉnh là các nút giao thông, còn các cạnh là các con đường.

Giả sử trên một hành trình bất kì tìm được, thì tải trọng xe cho phép trên hành trình này là limitlimit. Theo đề bài, limitlimit chính là trọng số của cạnh nhỏ nhất trên hành trình tìm được.

Ta nhận thấy rằng, nếu tìm được một hành trình đi từ 11 tới nn với tải trọng xe cho phép là limitlimit thì cũng có thể tìm được một hành trình đi từ 11 tới nn với tải trọng xe cho phép là [1...limit1][1...limit - 1]. Vì thế, ta có thể thực hiện tìm kiếm nhị phân trên tập kết quả để tìm ra giá trị limitlimit lớn nhất.

Với một giá trị limit (1limit105);limit \ (1 \le limit \le 10^5); ta cần xác định có tồn tại đường đi từ 11 tới nn mà trọng số của tất cả các cạnh đều phải lớn hơn hoặc bằng limitlimit. Do trọng số các cạnh trên đồ thị không âm, nên ta có thể sử dụng Dijkstra để xác định điều này (trong quá trình Dijkstra chỉ sử dụng các cạnh có trọng số lớn hơn hoặc bằng limitlimit).

Do n105n \le 10^5 nên ta sẽ sử dụng Dijkstra Heap kết hợp với danh sách kề để biểu diễn đồ thị.

Độ phức tạp: O(logw×max(m,n)×logn)O\big(\log w \times \text{max}(m, n) \times \log n\big).

Cài đặt

#include <bits/stdc++.h>
#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];

// Truy vết đường đi.
void print_result(int s, int t, int res, vector < int > &last_trace)
{  
    cout << res << '\n';
    
    vector < int > path;
    while (t != s)
    {
        path.push_back(t);
        t = last_trace[t];
    }
    path.push_back(s);
    reverse(path.begin(), path.end());

    for (int u: path)
        cout << u << ' ';
}

bool check(int n, int limit, vector < int > &last_trace)
{
    vector < int > trace(n + 1), d(n + 1, inf);
    vector < bool > is_free(n + 1, true);
    priority_queue < pi, vector < pi >, less < pi > > qu_min;
    d[1] = 0;
    qu_min.push({d[1], 1});

    while (!qu_min.empty())
    {
        int u = qu_min.top().second;
        int du = qu_min.top().first;
        qu_min.pop();

        if (u == n)
        {
            last_trace = trace;
            return true;
        }

        is_free[u] = false;

        for (auto e: adj[u])
        {
            int v = e.first, w = e.second;

            if (is_free[v] && w >= limit && d[v] > du + w)
            {
                d[v] = du + w;
                trace[v] = u;
                qu_min.push({d[v], v});
            }
        }
    }

    return false;
}

void solution(int n)
{
    int l = 0, r = 100000, res = 0;
    vector < int > last_trace(n + 1);
    while (l <= r)
    {
        int mid = (l + r) >> 1;

        if (check(n, mid, last_trace))
        {
            res = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }

    print_result(1, n, res, last_trace);
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    solution(n);

    return 0;
}

V. Tài liệu tham khảo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí