Bài toán tìm đường đi ngắn nhất tu 1 dinh năm 2024
Ta bắt đầu khởi tạo các mảng n phần tử: label, length, prev. Gán label[k] = 1, length[k] = -1 (inf), prev[k] = -1 với k chạy từ 0 -> n – 1. Gán length[first] = 0. Show Chọn đỉnh v trong mảng sao cho length[k] là nhỏ nhất. Sau đó gán label[k] = 0 (Đã đánh dấu). Tạo vòng lặp với biến chạy k, xét nếu label[k] = 1 (Chưa đánh dấu) và có đường đi từ v -> k: Nếu length[k] > length[v] + trọng số từ v -> k hoặc length[k] = inf, có nghĩa là nếu ta tìm được 1 đường từ v -> k là nhỏ nhất, hoặc là chưa tìm được đường nào ngắn nhất (inf) => Gán length[k] = length[v] + trọng số v -> k, prev[k] = v (Tạo vết chân đỉnh trước đó). Nếu label[last] = 0 (Đã đánh dấu đỉnh đến), kết thúc vòng lặp. Nếu không thì quay lại bước 2. VD: Ta có 1 đồ thị như sau 2. Viết và chạy thuật toánĐể đơn giản, trong phần này tôi dùng ma trận kề, và mỗi các đỉnh được đặt tên theo số thứ tự 0,1,2.
Output của thuật toán trên sẽ là:
3.Đánh giá độ phức tạpĐộ phức tạp của thuật toán trên sẽ là O(V2). Nếu ta sử dụng một hàng đợi ưu tiên (priority queue), ví dụ như Binary heap, và sử dụng danh sách kề thì độ phức tạp của thuật toán sẽ bị giảm xuống còn O((V+E)∗logV). Nguyên nhân là, với danh sách kề, thời gian để duyệt các cạnh và các đỉnh sẽ là O(E+V) thay vì O(V2) như ma trận kề. Ngoài ra, với binary heap, việc tìm đỉnh gần nhất ở
sẽ chỉ còn O(1) thay vì O(V). Vì thế ta cần nhập khoảng cách tới các đỉnh xung quanh vào binary heap bằng cách bỏ các đỉnh đó ra khỏi heap rồi thêm lại, cái này mất O(logV). Vậy cuối cùng độ phức tạp sẽ là O((V+E)∗logV). Trên đây là bài viết về "Tìm đường ngắn nhất bằng thuật toán Dijkstra". Tuỳ theo từng yêu cầu cụ thể mà bạn có thể lựa chọn cách làm hợp lý. Bài viết này đề cập về thuật toán Bellman-Ford. 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ế ví dụ như Google Maps. 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 thi đấu. 2. Bài toánCho đồ thị có hướng \(N\) đỉnh và \(M\) cạnh, và một đỉnh nguồn là đỉnh \(S\). Mỗi cạnh có trọng số nguyên. Trọng số này có thể âm hoặc dương hoặc bằng 0. Với mỗi đỉnh \(u\) từ \(1\) đến \(N\). Yêu cầu xuất kết quả tại mỗi đỉnh \(u\) như sau:
Input: Dòng đầu tiên gồm 3 số nguyên \(N, M, S\). \(M\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u, v, W\) biểu diễn một cạnh một chiều từ \(u\) đến \(v\) với trọng số là \(W\). Output: gồm \(N\) dòng cho biết đường đi ngắn nhất từ đỉnh \(S\) đến các đỉnh từ \(1\) đến \(N\) Giới hạn bài toán : \(N <= 1000, M <= 5000\) Sample Input 7 6 5 1 2 7 3 1 1 2 3 -9 3 6 1000 4 1 7 5 4 3 Sample Output -Infinity -Infinity -Infinity 3 0 -Infinity Impossible 3. Khái niệm chu trình âmChu trình âm là một chu trình trong đó tổng trọng số các cạnh là số âm. Ví dụ trong bài toán trên, ta có một chu trình âm \(1 – 2 – 3 – 1\) có tổng trọng số là \(7 – 9 + 1 = -1\). Nếu trên đường đi từ \(u\) đến \(v\) chứa chu trình âm thì độ dài đường đi ngắn nhất từ u đến v sẽ là âm vô cực. Vì vậy nên một số cặp đỉnh không tồn tại đường đi ngắn nhất do có chu trình âm trên đường đi giữa chúng (chỉ tồn tại đường đi có độ dài âm vô cực). Ví dụ: Ở đồ thị trên, đường đi ngắn nhất từ \(4\) đến \(6\) sẽ có cách đi là vô hạn lần qua chu trình âm đã nhắc đến, sau đó mới đi đến \(6\). Như vậy không có đường đi ngắn nhất. 4. Ý tưởng của thuật toánXét trường hợp đơn giản hơn, khi đồ thị không có trọng số âm (tức là đường đi ngắn nhất luôn tồn tại). Ở mỗi vòng lặp, ta duyệt qua tất cả cạnh \((u,v)\), so sánh đường đi từ \(S->v\) đã tìm được với đường đi \(S->u->v\) Ví dụ đồ thị sau: ta tìm được đường đi từ \(1->3\) có độ dài là \(4\), và đường đi từ \(1->2\) độ dài là \(2\). Như vậy ta có thể sử dụng cạnh \((2,3)\) để nối dài đường đi \(1->2\) thành \(1->2->3\) có độ dài bằng \(3\), ngắn hơn đường đi trực tiếp ta đã tìm được. Có thể chứng minh được rằng, vòng lặp trên cần thực hiện \(N−1\) lần, mỗi lần đi qua toàn bộ \(M\) cạnh, là sẽ đủ để tìm đường đi ngắn nhất. Nhận xét rằng một đường đi ngắn nhất bất kì sẽ không có đỉnh nào được đi lại quá một lần. Như vậy một đường đi ngắn nhất sẽ không có quá \(N−1\) cạnh. Việc thực hiện phép tính \(D_{v}=D_{u}+W_{u,v}\) cũng đồng nghĩa với thêm một cạnh \(u -> v\) vào hành trình đi từ \(s\) đến \(v\). Vậy mỗi \(D_{u}\) chỉ có thể được tối ưu tối đa \(N-1\) lần, và từ lần thứ \(N\) trở đi sẽ không thể tối ưu hơn được nữa. Cài đặt
Code
define fi firstdefine se seconddefine int long longdefine pii pairconst int inf = 1e18;
const int mx = 1e6 + 5;
vector Truy vết đường đi ngắn nhấtTa sẽ bắt đầu từ đỉnh \(u\), sau đó truy vết theo mảng trace ngược về S. vector 5. Các trường hợp có chu trình âmTại sao thuật toán Dijkstra không làm với đồ thị có trọng số âm?Đồ thị có trọng số âm có thể chứa chu trình âm, do đó đường đi ngắn nhất giữa một số cặp đỉnh sẽ là \(-infinity\). Thuật toán Dijkstra không có khả năng nhận biết chu trình âm, do đó thuật toán sẽ lặp vô hạn để tối ưu đường đi với chu trình đó. Thuật toán Bellman-Ford có thể xử lí được thêm trường hợp nhận biết chu trình âm, cũng như nhận biết nếu không tồn tại đường đi ngắn nhất đến một đỉnh. Nhận biết đường đi âm vô cựcNhận xét tiếp rằng, ta có thể chạy vòng quanh chu trình âm liên tục để được đường đi ngắn hơn. Như vậy thuật toán Bellman-Ford ở vòng lặp thứ \(N\) trở đi vẫn sẽ liên tục tối ưu được đường đi, thay vì dừng lại ở lần thứ \(N-1\). Ta chỉ cần chạy thuật toán Bellman-Ford thêm một lần nữa với \(N\) vòng lặp, những đỉnh nào vẫn còn tối ưu được ở lần chạy thứ hai sẽ tối ưu được mãi mãi, và đó là các đỉnh không tồn tại đường đi ngắn nhất. Code:
define fi firstdefine se seconddefine int long longdefine pii pairconst int inf = 1e18;
const int mx = 1e6 + 5;
vector Tìm chu trình âmMột số bài toán có thể yêu cầu ta tìm một chu trình âm bất kì trong đồ thị. Ta có thể chỉnh sửa thuật toán Bellman-Ford lại như sau: |