Đâ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(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),$ các đỉnh được đánh số từ $1$ tới $n$. Độ dài của đường đi ngắn nhất giữa hai đỉnh $s$ và $t$ được kí hiệu là $d(s, t),$ và nếu như không tồn tại đường đi từ đỉnh $s$ tới một đỉnh $t$ nào đó thì ta sẽ coi $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 $s$ cho trước tới một đỉnh $t$ cho trước trên đồ thị?

Input:

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

Ràng buộc:

• $1 \le n, m \le 10^5$.
• $1 \le u \ne v \le n$.
• $|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 $s$ và $t$. Nếu không tồn tại đường đi thì in ra $-1$.
• Dòng thứ hai in ra các đỉnh trên đường đi ngắn nhất từ $s$ tới $t$ 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 $s$ 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ọi $P = \{v_1, v_2, \dots, v_k\}$ là một đường đi ngắn nhất từ $v_1$ tới $v_k$. Khi đó $\forall i, j: 1 \le i \le j \le k,$ đoạn đường $P_{ij} = \{v_i, v_{i + 1}, \dots, v_j\}$ là một đường đi ngắn nhất từ $v_i$ tới $v_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,$ gọi $d[v]$ là độ dài đường đi ngắn nhất từ $s$ tới $v$. Ban đầu ta khởi tạo:

• $d[s] = 0$.
• $d[v] = +\infty; \forall v \ne s$.

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

$$d[v] = d[u] + w_{u, v}$$

Tức là, nếu độ dài đường đi từ $s$ tới $v$ hiện tại bị lớn hơn độ dài đường đi từ $s$ tới $u$ cộng với trọng số đi từ $u$ tới $v$ thì ta sẽ hủy bỏ đường đi cũ và coi đường đi mới từ $s$ tới $v$ chính là đường đi từ $s$ tới $u$ rồi từ $u$ tới $v$. 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]$ 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]$ chính là độ dài ngắn nhất của đường đi từ $s$ tới $v$ đi qua không quá $0$ cạnh.

Giả sử tại bước lặp thứ $i \ (i≥1), d[v]$ đã bằng độ dài ngắn nhất đi từ $s$ tới $v$ qua không quá $i - 1$ cạnh. Đường đi từ $s$ tới $v$ qua không quá $i$ cạnh sẽ được thành lập bằng cách: Lấy một đường đi từ $s$ tới một đỉnh $u$ nào đó kề với $s$ (qua không quá $i - 1$ cạnh), rồi đi tiếp tới $v$ bằng cung trực tiếp $(u \to v),$ do đó đường đi ngắn nhất từ $s$ tới $v$ qua không quá $i$ 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ừ $s$ tới $v$ qua không quá $i - 1$ cạnh (ở bước trước).
• Độ dài đường đi ngắn nhất từ $s$ tới $u$ (qua không quá $i - 1$ cạnh) cộng với trọng số cung $(u \to v)$.

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

$$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,$ ta có $d[v]$ bằng độ dài đường đi ngắn nhất từ $s$ tới $v$ qua không quá $n - 1$ cạnh. Vì đồ thị không có chu trình âm, do đó sẽ có một đường đi ngắn nhất từ $s$ tới $v$ là đường đi cơ bản (đi qua không quá $n - 1$ cạnh, do đường đi cơ bản là đường đi không có đỉnh lặp lại, mà đồ thị có $n$ đỉnh thì cần đi qua tối đa $n - 1$ cạnh để đạt được đường đi cơ bản). Tức là $d[v]$ sẽ là độ dài đường đi ngắn nhất từ $s$ tới $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 - 1$ bước.

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

$$trace[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],$ xét lại các cung $(u \to v)$ của đồ thị.
• Nếu như vẫn tồn tại một cung khiến cho $d[v]$ nào đó có thể tối ưu hóa hơn nữa $(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ừ $s$ tới $t$.

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ị $10^{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,$ ta có thể thực hiện thêm một số bước dưới đây:

• Bước 1: Tìm ra đỉnh $x$ mà $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 - 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ừ $s$ tới được nó, bằng cách đi ngược lại $x = trace[x]$ đủ $n$ lần.
• Bước 3: Từ đỉnh $x,$ tìm ra các đỉnh thuộc chu trình âm chứa $x$ bằng cách liên tục ghi nhận $x$ rồi đi ngược về $trace[x]$ tới khi quay lại đỉnh $x$ ở bước $2$ 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\big(|E|\big)$.

Về mặt thời gian, dễ thấy thuật toán lặp không quá $n - 1$ lần, và mỗi lần phải lặp qua cả $m$ cạnh để tối ưu các $d[v]$. Vì thế độ phức tạp tính toán tổng quát là $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,$ đặt $d[v]$ là độ dài đường đi ngắn nhất từ $s$ tới $v$. Thuật toán Ford Bellman khởi tạo $d[s] = 0$ và $d[v] = +\infty; \forall v: v \ne s;$ rồi tối ưu hóa dần các giá trị $d[v]$ theo công thức: $d[v] = \text{min}\big(d[v], d[u] + w_{u, v}\big)$. Như vậy, nếu ta dùng một đỉnh $u$ để tối ưu hóa đỉnh $v,$ và sau đó ở một bước nào đấy $d[u]$ lại được tối ưu thêm, thì mọi $d[v]$ liên quan tới $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 \to v)$ để tối ưu hóa $d[v],$ ta sẽ chọn ngay một đỉnh $u$ mà $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 $v$ kề với nó. Đỉnh $u$ được chọn này sẽ là đỉnh $u$ có $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,$ gọi $d[v]$ là độ dài đường đi ngắn nhất từ $s$ tới $v$. Ban đầu khởi gán $d[s] = 0$ và $d[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 $\text{is\_free}[u] = \text{TRUE}$ hoặc $\text{is\_free}[u] = \text{FALSE}$ tùy theo $u$ còn có thể tối ưu tiếp hoặc không. Ban đầu ta có $\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 $t$ được cố định, hoặc tất cả các đỉnh $u$ còn có thể tối ưu tiếp lại đều có $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 $u$ có $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 $u$ vừa lấy ra, xét tất cả đỉnh $v$ kề với nó và sửa lại giá trị $d[v]$ theo công thức:

  $$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],$ 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] = +\infty$).

Chứng minh:

Tại sao ở mỗi bước lặp, đỉnh $u$ với $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 $u$ như vậy vẫn còn có thể tối ưu thêm, thì phải tồn tại một đỉnh $u_1$ nào đó với $\text{is\_free}[u_1] = \text{TRUE}$ sao cho $d[u] > d[u_1] + w_{u_1, u}$. Do trọng số $w_{u_1, u}$ không âm nên chắc chắn $d[u_1] > d[u],$ điều này trái với cách chọn $d[u]$ là nhỏ nhất lúc đầu.

Vậy đỉnh $u$ với $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]$ là đỉnh liền trước $v$ trên đường đi ngắn nhất từ $s$ tới $v$. Mỗi khi cập nhật một giá trị $d[v] = d[u] + w_{u, v}$ thì đồng thời cập nhật luôn $trace[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)$.

Trong trường hợp xấu nhất, thuật toán đơn giản này sẽ cần $n$ lần cố định các $d[v]$ và mất thêm $O(n)$ để tìm đỉnh ra đỉnh $u$ có $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(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 $10000$ đỉ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 $u$ có $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 $v$ vẫn còn có thể tối ưu tiếp kèm theo giá trị $d[v]$ hiện tại của nó.
• Phần tử với $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)$ (đỉnh xuất phát cùng với nhãn bằng $0$ 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]$ được đưa lên đầu hàng đợi (tức là đường đi tới đỉnh $t$ đã được tối ưu):

• Bước 1: Lấy ra đỉnh $u$ ở đầu hàng đợi, đỉnh này chính là đỉnh có $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 $\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,$ tối ưu các đỉnh $v$ kề với nó mà có $\text{is\_free}[v] = \text{TRUE}$ theo công thức: $d[v] = \text{min}\big(d[v], d[u] + w_{u, v}\big);$ sau đó đưa phần tử $(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\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 $u$ 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\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 = \{a_1, a_2, \dots, a_n\};$ sau đó xin quyết định của nhà vua cho $m$ 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 $S$. Nhà vua đã đưa ra quyết định nhanh chóng: Với mỗi dãy con $S_i,$ ngài đưa ra một số nguyên $k_i$ rồi thông báo tổng của dãy con $S_i$ lớn hơn hoặc nhỏ hơn $k_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ố $S$ 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ố $S$ ban đầu mình nhận được. Vì vậy, nhà vua quyết định đưa ra một dãy $S$ 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 $S$ 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, m$ - độ dài của dãy $S$ nhà vua nhận được và số lượng quyết định nhà vua đã đưa ra.
  • Trên $m$ dòng tiếp theo, mỗi dòng chứa một bộ bốn giá trị $s_i, n_i, o_i, k_i$ - với $o_i$ là gt 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 $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ị $k_i$ theo thể hiện của $o_i$.
• Dòng cuối cùng của đầu vào chứa duy nhất số $0$ - thể hiện kết thúc việc nhập dữ liệu.

Ràng buộc:

• $1 \le n \le 100$.
• $1 \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 $S$ 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) = \sum_{i = 1}^k a_i$ và coi $sum(0) = 0$.

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

$$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 = \{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ị $\big\{sum(1), sum(2), \dots, sum(n)\big\}$ thỏa mãn điều kiện $(*)$ với mọi $i = 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,$ nó tương đương với $a \le b - 1$ và tương tự, $a > b$ tương đương với $a \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,$ ta có một dãy các ràng buộc ở dạng:

  $$\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(x_i) - sum(y_i) > k_i$ thì ta đưa nó về $sum(y_i) - sum(x_i) \le -k_i - 1;$ ngược lại thì đưa về $sum(x_i) - sum(y_i) \le k_i - 1$. Ở đây $x_i = s_i - 1$ và $y_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ừ $0$ tới $n,$ và mỗi điều kiện được thể hiện bởi một cung nối từ đỉnh $y_i$ tới đỉnh $x_i$ trên đồ thị (hoặc ngược lại) với trọng số là $c_i$. Riêng đỉnh $0$ (đỉ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à $0$.

Sau khi xây dựng đồ thị, nếu như đồ thị không có chu trình âm và tất cả các $c_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ố $S$ 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 + 1$ do đỉnh $0$ vẫn tồn tại trong đồ thị ban đầu.

Độ phức tạp: $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 $n$ nút giao thông được đánh số từ $1$ tới $n$ và $m$ đ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 $1$ tới nút giao thông $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 $1$ tới nút $n$ 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,m$.
• Trên $m$ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương $u,v,w$ cho biết có con đường hai chiều với giới hạn tải trọng là $w$ nối giữa hai vùng $u$ và $v \ (1≤u,v≤n)$.

Ràng buộc:

• $2≤ n ≤ 10^5$.
• $1≤ m ≤2×10^5$.
• $1≤ w ≤ 10^4$.

Output:

• Dòng thứ nhất ghi một số nguyên $w$ 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à $limit$. Theo đề bài, $limit$ 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ừ $1$ tới $n$ với tải trọng xe cho phép là $limit$ thì cũng có thể tìm được một hành trình đi từ $1$ tới $n$ với tải trọng xe cho phép là $[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ị $limit$ lớn nhất.

Với một giá trị $limit \ (1 \le limit \le 10^5);$ ta cần xác định có tồn tại đường đi từ $1$ tới $n$ mà trọng số của tất cả các cạnh đều phải lớn hơn hoặc bằng $limit$. 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 $limit$).

Do $n \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\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

• https://cp-algorithms.com/graph/bellman_ford.html#shortest-path-faster-algorithm-spfa
• https://cp-algorithms.com/graph/dijkstra.html
• https://cp-algorithms.com/graph/dijkstra_sparse.html
• Tài liệu giáo khoa chuyên Tin quyển 2 - thầy Hồ Sĩ Đàm.
• Giải thuật và Lập trình - thầy Lê Minh Hoàng.