Bài toán đường đi ngắn nhất - Phần 2

Tổng quan

Bài viết này thuộc phần thứ 2 trong loạt bài về Bài toán đường đi ngắn nhất trên đồ thị. Bạn có thể tìm đọc phần 1 tại đây.

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

Trước đây chúng ta đã thảo luận về thuật toán Floyd-Warshall, một giải pháp hiệu quả cho bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh. Tuy nhiên, thuật toán này gặp một số hạn chế lớn về độ phức tạp, lên đến O(n^3), nên chỉ phù hợp với các đồ thị nhỏ.

Trong nhiều tình huống thực tế, chúng ta chỉ cần tìm ra đường đi ngắn nhất từ một đỉnh xuất phát (single-source shortest path) đến các đỉnh khác. Đây là bài toán phổ biến và thuật toán Floyd-Warshall chỉ là một biến thể của nó. Cụ thể, bài toán được nêu như sau:

Cho đồ thị có hướng G = (V, E, w) với các đỉnh được đánh số từ 1 đến n. Độ dài đường đi ngắn nhất giữa hai đỉnh s và t được ký hiệu là d(s, t). Nếu không tồn tại đường đi từ s đến t, chúng ta coi d(s, t) = ∞.

Yêu cầu: Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t.

Đầu vào:

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

Đầu ra:

• Dòng đầu tiên in ra độ dài đường đi ngắn nhất. Nếu không tồn tại đường đi, in ra -1.
• Dòng thứ hai in ra các đỉnh trên đường đi ngắn nhất từ s đến t, tách nhau bởi dấu cách.

Ví dụ đầu vào:

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

Ví dụ đầu ra:

15
1 2 3 6 5 4

Bài toán trên yêu cầu chúng ta tìm đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại. Ở phần này, chúng ta sẽ tìm hiểu hai thuật toán phổ biến để giải quyết bài toán này: Dijkstra và Ford-Bellman. Lưu ý rằng các thuật toán này được triển khai trên đồ thị có hướng. Trong trường hợp đồ thị vô hướng, chúng ta có thể biến đổi nó thành đồ 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 khảo sát đề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 đều là những đường đi ngắn nhất.

Định lý 1.1: Cho đồ thị có trọng số G = (V, E, w), có P = {v1, v2, …, vk} là một đường đi ngắn nhất từ v1 đến vk. Khi đó, với mọi i, j: 1 ≤ i ≤ j ≤ k, đoạn đường P_ij = {vi, vi+1, …, vj} cũng là một đường đi ngắn nhất từ vi đến vj.

Bởi tính chất bài toán con tối ưu, đa số các thuật toán tìm đường đi ngắn nhất đều là các giải thuật quy hoạch động (như Floyd) hoặc tham lam (như Dijkstra).

Trong trường hợp đồ thị có chu trình âm (chu trình có trọng số âm), khoảng cách giữa một số cặp đỉnh có thể không xác định, bởi vì bạn có thể lặp lại chu trình này một cách bất tận và làm cho độ dài đường đi giảm xuống không hạn chế. Do đó, trong phần này, chúng ta chỉ tập trung vào các thuật toán tốt cho đồ 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 đồ thị không có chu trình âm, thuật toán Ford-Bellman sử dụng ý tưởng đơn giản: 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:

• d[s] = 0.
• d[v] = +∞ với mọi v ≠ s.

Các giá trị d[v] sẽ được tối ưu thông qua lặp qua mọi cặp đỉnh u, v. Nếu phát hiện một d[v] lớn hơn d[u] + w(u, v), thì cập nhật lại d[v] bằng d[u] + w(u, v).

Thuật toán sẽ kết thúc khi không còn giá trị nào d[v] nào có thể tối ưu hơn.

Chương trình:

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 ta sẽ sử dụng mảng trace[v] để lưu lại đỉnh liền trước của v trong đường đi ngắn nhất từ s tới v. Khi cập nhật d[v], sẽ đồng thời cập nhật trace[v] = u.

Cài đặt

...
void bellman_ford(int n, int m, int s, int t, vector < edge > &edges_list) {
    ...
}

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

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

Trong trường hợp đồ thị có trọng số không âm, thuật toán Dijkstra hoạt động hiệu quả hơn nhiều so với Ford-Bellman. Lý do là ở mỗi vòng lặp, nó không cần phải kiểm tra lại mọi cung, mà chỉ chọn một đỉnh có giá trị nhỏ nhất và cập nhật. Nhờ vậy, thuật toán không phát sinh những giá trị phụ không cần thiết.

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

Để cải thiện độ phức tạp cho đồ thị lớn hơn, chúng ta sử dụng cấu trúc dữ liệu Heap hoặc queue ưu tiên để tìm đỉnh có d[u] nhỏ nhất một cách nhanh chóng.

void dijkstra_heap(int n, int m, int s, int t) {
    ... // Hàng đợi ưu tiên kích hoạt ở đây
}

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

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

2. Giao thông

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

• https://cp-algorithms.com/graph/bellman_ford.html
• https://cp-algorithms.com/graph/dijkstra.html
• Tài liệu giáo khoa chuyên Tin.

source: viblo