¶ Các thuật toán tìm đường đi ngắn nhất - Phần 1

Tác giả:

• Trần Hoài An - THPT Hoàng Lê Kha, Tây Ninh
• Nguyễn Đức Kiên - Đại học Công nghệ - ĐHQGHN

Reviewer:

• Nguyễn Xuân Tùng - Đại học Quốc Tế, Đại học Quốc gia Thành phố Hồ Chí Minh

Chuỗi bài viết: Phần 1 • Phần 2 • Phần 3

¶ Giới thiệu

Bài toán tìm đường đi ngắn nhất trên đồ thị là một trong những bài toán đa dạng, có nhiều ứng dụng thực tế như trong Google Maps, các bài toán networking, .... Các dạng bài về tìm đường đi ngắn nhất cũng thường xuyên có mặt trong các kì thi lập trình.

Chuỗi bài viết này sẽ giới thiệu một số thuật toán cơ bản của dạng bài tìm đường đi ngắn nhất:

• Sử dụng Sắp xếp Topo.
• Thuật toán Dijkstra.
• Thuật toán Bellman - Ford.
• Thuật toán Floyd-Warshall (còn gọi là thuật toán Floyd).
• Thuật toán SPFA.

Mỗi thuật toán đều có ưu điểm, hạn chế riêng và phù hợp với các bài toán cụ thể. Cùng tìm hiểu và so sánh để lựa chọn giải pháp tối ưu cho từng bài toán.

Trong bài viết này, ta sẽ đi sâu vào hai thuật toán đầu tiên:

• Sử dụng Sắp xếp Topo.
• Thuật toán Dijkstra.

¶ Đường đi ngắn nhất sử dụng Sắp xếp Topo

Trong trường hợp đồ thị có hướng và không có chu trình (DAG - Directed Acyclic Graph), ta sử dụng sắp xếp topo để xây dựng một thuật toán quy hoạch động tìm đường đi ngắn nhất

¶ Bài toán

Cho một đồ thị có hướng với đỉnh (được đánh số từ đến ), cạnh có hướng, có trọng số, và một đỉnh nguồn . Trọng số cạnh từ đến là . Biết rằng đồ thị đã cho không có chu trình. Yêu cầu tìm ra đường đi ngắn nhất từ đỉnh tới tất cả các đỉnh còn lại (hoặc cho biết nếu không có đường đi).

¶ Ý tưởng của thuật toán

¶ Thứ tự topo

Nhắc lại, thứ tự topo của một đồ thị có hướng là một thứ tự sắp xếp của các đỉnh sao cho với mọi cung từ đỉnh đến đỉnh trong đồ thị, luôn nằm trước. Để đồ thị tồn tại thứ tự topo, nó phải là DAG. Một DAG có thể có nhiều thứ tự topo khác nhau.

Để tìm thứ tự topo của một DAG, có một cách rất đơn giản là xây dựng danh sách ngược bằng cách tiến hành DFS từ tất cả các đỉnh nếu đỉnh đó chưa được thăm trước đó, và đẩy nó vào danh sách sau khi đã thăm mọi đỉnh có thể thăm từ nó. Chi tiết về cách làm này bạn đọc có thể tham khảo bài viết sắp xếp topo của VNOI.

Quá trình tìm thứ tự topo do đó có độ phức tạp là .

¶ Tìm đường đi ngắn nhất

Gọi là đường đi ngắn nhất đến đỉnh . Một cách tự nhiên, ta vẫn sẽ tính bằng các đỉnh kề (có cạnh từ đỉnh đến đỉnh ):

ề

Ta biết rằng chỉ tồn tại đường đi từ đỉnh có thứ tự topo nhỏ hơn đỉnh có thứ tự topo lớn hơn. Vì vậy, để tìm đường đi ngắn xuất phát từ một đỉnh, ta chỉ cần xét các đỉnh theo đúng thứ tự topo từ đỉnh xuất phát, và cập nhật các đỉnh kề với .

Về độ phức tạp, ta mất thời gian để tìm thứ tự topo và mất thêm thời gian để tiến hành dp, ngoài ra thêm thời gian nữa cho việc truy vết. Tổng độ phức tạp thời gian là . Độ phức tạp không gian nếu cài đặt bằng danh sách kề như ở dưới đây là .

¶ Cài đặt

int n, m, s; vector<vector<pair <int, int> > > adj; vector <int> topo, trace, topoId; vector <long long> d; vector <bool> visit; void dfs(int u) { visit[u] = 1; for (auto p : adj[u]) { auto v = p.first; if (!visit[v]) { dfs(v); } } topo.push_back(u); } long long spDAG() { for (int u = 0; u < n; u++) { if (!visit[u]) { dfs(u); } } reverse(topo.begin(), topo.end()); for (int i = 0; i < n; i++) { topoId[topo[i]] = i; } fill(d.begin(), d.end(), INF); d[s] = 0; for (int i = topoId[s]; i < n; i++) { int u = topo[i]; for (auto p : adj[u]) { int v = p.first; int w = p.second; if (d[v] > d[u] + w) { d[v] = d[u] + w; trace[v] = u; } } } return *min_element(d.begin(), d.end()); } vector<int> path() { vector<int> ret; if (d[t] != INF) { return ret; } int u = t; while (u != s) { ret.push_back(u); u = trace[u]; } ret.push_back(u); reverse(ret.begin(), ret.end()); return ret; }

¶ Chú ý thêm

Ta thấy rằng, dấu của trọng số không ảnh hưởng đến thuật toán. Miễn đồ thị đã cho là DAG, ta luôn có thể tìm được đường đi ngắn nhất

Ngoài tìm được đường đi ngắn nhất từ một đỉnh, bằng cách quy hoạch động dựa trên thứ tự topo của một DAG ta có thể tìm được:

• Đường đi dài nhất từ một đỉnh đến các đỉnh khác (thay thành )
• Đường đi ngắn nhất hoặc dài nhất trong tất cả các đường đi trên đồ thị (thêm một đỉnh giả nối với các đỉnh có bậc vào bằng và tìm đường đi ngắn nhất từ đỉnh này)
• Đếm số đường đi từ một đỉnh hoặc trên cả DAG

Tham khảo tại bài viết Quy hoạch động trên DAG.

¶ Thuật toán Dijkstra

Thuật toán Dijkstra dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path) trên đồ thị có trọng số không âm.

¶ Bài toán.

Cho một đồ thị có hướng với đỉnh (được đánh số từ đến ), cạnh có hướng, có trọng số, và một đỉnh nguồn . Trọng số của tất cả các cạnh đều không âm. Yêu cầu tìm ra đường đi ngắn nhất từ đỉnh tới tất cả các đỉnh còn lại (hoặc cho biết nếu không có đường đi).

Sample Input

7 8 0 0 2 7 0 1 1 0 3 4 2 5 8 5 3 3 4 5 6 1 4 3 2 4 3

Sample Output

0 1 7 4 4 10 -1

Hình ảnh của Test ví dụ. Ở đồ thị này, đỉnh nguồn là đỉnh , đường đi ngắn nhất từ đến các đỉnh đến là . Riêng đỉnh không có đường đi đến.

¶ Ý tưởng của thuật toán.

Ý tưởng chính của thuật toán Dijkstra là tối ưu hóa đường đi bằng cách xét các cạnh , so sánh hai đường đi sẵn có với đường đi .

Thuật toán sẽ duy trì một mảng chứa đường đi ngắn nhất từ đến tất cả các đỉnh. Ở mỗi bước, chọn đỉnh với đường đi có trọng số nhỏ nhất trong số các đỉnh chưa được xử lý. Sau đó, thuật toán kiểm tra và cập nhật đường đi bằng cách thử đường đi . Vì là đường đi ngắn nhất được chọn nên đường đi này không cần kiểm tra lại và được đánh dấu là đã xử lý xong. Thuật toán tiếp tục lặp các bước trên với các đỉnh còn lại cho đến khi tất cả đỉnh đều được xử lý.

¶ Minh họa thuật toán

Ta sẽ minh họa thuật toán bằng một đồ thị như hình. Định nghĩa:

• là đường đi ngắn nhất từ đỉnh nguồn đên đỉnh đã tìm được.
• nhận hai giá trị , cho biết đỉnh đã được chọn để tối ưu chưa.

Đỉnh được tô đen (đỉnh 0) sẽ là đỉnh nguồn.

Ban đầu, ,

• Bước 1: Thuật toán sẽ chọn đỉnh , vì là nhỏ nhất thỏa mãn . Tiến hành tối ưu các cạnh đi ra:
  • Cạnh : cập nhật
  • Cạnh : cập nhật

Sau bước này, ,

• Bước 2: thuật toán sẽ chọn ra đỉnh , có là nhỏ nhất thỏa mãn . Tiến hành tối ưu các cạnh đi ra:
  • Cạnh : cập nhật
  • Cạnh : cập nhật

Sau bước này, ,

• Bước 3: thuật toán sẽ chọn ra đỉnh , có là nhỏ nhất thỏa mãn . Tiến hành tối ưu các cạnh đi ra:
  • Cạnh : cập nhật

Sau bước này, ,

• Bước 4: thuật toán sẽ chọn đỉnh . Không có cạnh nào đi ra.

Đến đây, tất cả các đỉnh đều đã được đánh dấu. Thuật toán kết thúc. Đường đi ngắn nhất tìm được từ đỉnh là .

¶ Cài đặt

Ở thuật toán này, ta sẽ lưu đồ thị dưới dạng danh sách kề. Ta định nghĩa như sau:

• là đường đi ngắn nhất từ . Ban đầu khởi tạo với mọi , riêng .
• là trọng số cạnh trên đường đi từ .
• là mảng đánh dấu các đỉnh đã được xử lí chưa. Ban đầu tất cả các giá trị đều là false.
• Trong trường hợp bài toán yêu cầu chũng ta truy vết, ta có thể định nghĩa thêm một mảng , trong đó là đỉnh nằm trước đỉnh trên đường đi ngắn nhất từ đến .

Ta sẽ lặp lần quá trình sau:

• Tìm đỉnh có nhỏ nhất và .
• Sau khi tìm được đỉnh , ta xét các đỉnh kề với đỉnh và tiến hành tối ưu hóa : nếu thì .
  • Nếu việc tối ưu hóa diễn ra, ta sẽ cập nhật .
• Đánh dấu , nghĩa là đỉnh đã được xử lí xong

¶ Độ phức tạp thuật toán

Trong quá trình tính toán, ta thực hiện lần lặp:

• Bước đầu tiên có độ phức tạp mỗi lần lặp.
• Bước thứ hai có tổng độ phức tạp qua tất cả các lần lặp

Như vậy độ phức tạp của cách cài đặt cơ bản sẽ là .

Code:

const long long INF = 2000000000000000000LL; struct Edge{ int v; long long w; }; void dijkstra(int n, int S, vector<vector<Edge>> E, vector<long long> &D, vector<int> &trace) { D.resize(n, INF); trace.resize(n, -1); vector<bool> P(n, 0); D[S] = 0; for (int i = 0; i < n; i++) { int uBest; // tìm đỉnh u chưa dùng, có khoảng cách nhỏ nhất long long Max = INF; for (int u = 0; u < n; u++) { if(D[u] < Max && P[u] == false) { uBest = u; Max = D[u]; } } // cải tiến các đường đi qua u int u = uBest; P[u] = true; for(auto x : E[u]) { int v = x.v; long long w = x.w; if(D[v] > D[u] + w) { D[v] = D[u] + w; trace[v] = u; } } } }

¶ Cải tiến đối với đồ thị thưa

• Nhận xét rằng bước đầu tiên: "Tìm đỉnh có nhỏ nhất và ", có thể được cải tiến. Ta có thể sử dụng cấu trúc dữ liệu Heap (cụ thể là Min Heap) hoặc cây nhị phân tìm kiếm để cải tiến bước này.

  • Mỗi lần chọn cạnh để tối ưu hóa , ta đẩy cặp vào trong Heap. sử dụng cạnh sẽ có tổng độ phức tạp là
  • Để tìm đỉnh có nhỏ nhất, ta chỉ cần liên tục lấy phần tử trên cùng trong Heap ra, cho đến khi gặp đỉnh thỏa mãn . cần lấy ra tối thiểu lần để lấy được tất cả đỉnh sẽ có tổng độ phức tạp là

• Do đó, độ phức tạp của thuật toán sau khi cải tiến là .

Lưu ý rằng với đồ thị dày cạnh thì cải tiến sử dụng Min Heap không tốt hơn cài đặt cơ bản. Khi đó, độ phức tạp của hai cách cài đặt có dạng như sau:

• Cách cài đặt cơ bản: .
• Cách cài đặt cải tiến: .

Tuy nhiên, thực tế các bài toán lập trình thi đấu ta thường gặp sẽ giới hạn nên nhìn chung khi thuật toán Min Heap với độ phức tạp luôn tốt hơn cả.

Code:

const long long INF = 2000000000000000000LL; struct Edge{// kiểu dữ liệu tự tạo để lưu thông số của một cạnh. int v; long long w; }; struct Node{// kiểu dữ liệu để lưu đỉnh u và độ dài của đường đi ngắn nhất từ s đến u. int u; long long Dist_u; }; struct cmp{ // Vì priority_queue mặc định để giá trị lớn nhất lên đầu // Nên b sẽ đặt lên trước a trong priority_queue chỉ khi a < b // Trong trường hợp này, ta cần a.Dist_u > b.Dist_U bool operator() (Node a, Node b) { return a.Dist_u > b.Dist_u; } }; void dijkstraSparse(int n, int s, vector<vector<Edge>> &E, vector<long long> &D, vector<int> &trace) { D.resize(n, INF); trace.resize(n, -1); vector<bool> P(n, 0); D[s] = 0; priority_queue<Node, vector<Node>, cmp> h; // hàng đợi ưu tiên, sắp xếp theo dist[u] nhỏ nhất trước h.push({s, D[s]}); while(!h.empty()) { Node x = h.top(); h.pop(); int u = x.u; if(P[u] == true) // Đỉnh u đã được chọn trước đó, bỏ qua continue; P[u] = true; // Đánh dấu đỉnh u đã được chọn for(auto e : E[u]) { int v = e.v; long long w = e.w; if(D[v] > D[u] + w) { D[v] = D[u] + w; h.push({v, D[v]}); trace[v] = u; } } } }

¶ Tìm lại đường đi ngắn nhất

Để tìm lại đường đi ngắn nhất từ về , ta sẽ bắt đầu từ đỉnh , sau đó truy vết theo mảng ngược về .

vector<int> trace_path(vector<int> &trace, int S, int u) { if (u != S && trace[u] == -1) return vector<int>(0); // không có đường đi vector<int> path; while (u != -1) { // truy vết ngược từ u về S path.push_back(u); u = trace[u]; } reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S return path; }

¶ Tổng kết

Bảng so sánh các thuật toán được đề cập:

Thuật toán Bài toán Độ phức tạp DP theo thứ tự topo Một nguồn Dijkstra Một nguồn Dijkstra + Min Heap Một nguồn

Heap không phải là cấu trúc dữ liệu duy nhất có thể sử dụng khi cài đặt Dijkstra dành cho đồ thị thưa. Ta có thể sử dụng bất cứ cấu trúc dữ liệu nào hỗ trợ các thao tác "xóa khỏi tập hợp", "cập nhật phần tử trong tập hợp", "tìm phần tử nhỏ nhất trong tập hợp". Do đó, các cây tìm kiếm nhị phân (ví dụ như std::set trong C++) cũng là một lựa chọn khi cài đặt thuật toán này.

Để khám phá thêm những thuật toán thú vị khác để tìm đường đi ngắn nhất trên đồ thị, mời bạn tiếp tục theo dõi phần 2 của chuỗi bài viết này.

¶ Bài tập vận dụng

Đồ thị dạng DAG:

• CSES - Longest Flight Route
• CSES - Game Routes

Thuật toán Dijkstra:

• Kattis - shortestpath1
• Codeforces - Dijsktra? (truy vết đường đi)
• CSES - Flight Discount
• Codeforces - Reducing Delivery Cost
• Các bài theo tag trên VNOJ