Trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu về thuật toán Floyd-Warshall trong tìm kiếm đường đi ngắn nhất trên đồ thị. Hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán có thể coi là thuật toán phổ biến nhất trong tìm kiếm đường đi ngắn nhất. Để biết cụ thể, hãy cùng nhau bắt đầu bài học nào! Show Nội dungĐể có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
Thuật toán DijkstraBài toán đặt raTa có một bài toán như sau: Cho một đồ thị có hướng gồm đỉnh (đánh số từ 1 đến), cạnh có hướng và có trọng số là số nguyên không âm. Cho một đỉnh, hãy tìm độ dài đường đi ngắn nhất từ đỉnh đến tất cả các đỉnh còn lại. Nếu như không tồn tại đường đi giữa hai đỉnh, in ra -1. Input: Output: Ví dụ: Input Output 7 8 1 1 2 4 1 3 5 1 4 2 4 2 1 4 6 4 3 5 3 6 5 1 1 5 8 0 3 5 2 7 6 -1 Giải thích ví dụ: Đây là đồ thị minh hoạ cho ví dụ trên _howkteam_vn.png) Ý tưởngÝ tưởng của Dijkstra về cơ bản khá giống với thuật toán Floyd. Với một cạnh nối liền hai đỉnh và, ta sẽ so sánh độ dài đường đi trước đây với đường. Tại mỗi bước, ta sẽ chọn ra một đỉnh mà ta biết chắc chắn đường đi từ là đường đi ngắn nhất. Sau đó, ta sẽ xét tất cả các đỉnh mà có cạnh liên kết trực tiếp rồi tối ưu đường đi dựa trên đường đi. Cách cài đặtTrước hết, để thể hiện một cạnh, ta sẽ sử dụng các vector với kiểu dữ liệupair<int, int>. pair là một cấu trúc cho phép ta lưu trữ hai phần tử. Ta có thể truy cập vào 2 phần tử củapair thông qua hai phương thức first và second. Ví dụ: ` include<bits/stdc++.h>using namespace std; int main(){ }
`Ta sẽ cần khởi tạo hai mảng với ý nghĩa như sau:
\==> Trong ví dụ trên, ta thấy có tối đa cạnh, mỗi cạnh có trọng số không quá nên độ dài một đường đi không quá. Giá trị khi này có thể là bất cứ giá trị nào lớn hơn hoặc bằng. Thuật toán sẽ diễn ra như sau:
Minh hoạMình sẽ minh họa thuật toán bằng một đồ thị cơ bản sau với đỉnh nguồn là đỉnh 1: _howkteam_vn.png)
Code cơ bảnCode` include<bits/stdc++.h>using namespace std; typedef long long ll; const int MaxN = 1 + 1e2; const ll INF = 1e18; int n, m, s; bool mark[MaxN]; ll dist[MaxN]; vector<pair<int, int>> adj[MaxN]; void Dijkstra(int s){ }
int main(){ }
`Độ phức tạpTa thấy trong đoạn code trên, ta có một vòng lặp ngoài cùng có độ phức tạp. Trong vòng lặp đó lại tồn tại 2 vòng lặp con. Vòng lặp thứ nhất để tìm ra đỉnh có dist[u] nhỏ nhất sẽ mất độ phức tạp . Tuy nhiên, vòng lặp thứ hai để tìm các đỉnh có cạnh kề với đỉnh u sẽ chỉ mất trong cả bài toán. Lí do là vì mỗi cạnh sẽ chỉ được duyệt qua duy nhất 1 lần. Do đó, độ phức tạp tổng thể của chương trình là . Code cải tiếnÝ tưởngTa thấy với độ phức tạp trên thì bài toán vẫn chưa được giải quyết trọn vẹn và lời giải sẽ cần được tối ưu thêm. Bây giờ hãy cùng xem xét các yếu tố có thể tối ưu được của bài toán. Vòng lặp dùng để duyệt và xét tất cả các cạnh sẽ luôn phải xảy ra. Do đó, vòng lặp này không thể tối ưu thêm nữa. Ta sẽ xét đến vòng lặp dùng để tìm ra đỉnh u có dist[u] nhỏ nhất. Ta thấy ngay việc dùng vòng lặp để tìm ra phần tử nhỏ nhất trong một tập hợp là một điều khá “ngu ngốc”. Ở những bài học trước, mình đã giới thiệu cho các bạn về một cấu trúc dữ liệu có thể tìm ra phần tử nhỏ nhất nhanh chóng. Các bạn có còn nhớ nó không? Nó chính là priority_queueđó. Ta sẽ dùng priority_queuelưu trữ các pair<long long,int>, trong đó giá trị first là độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh u, giá trị second là đỉnh u. Khipriority_queue so sánh cácpair<> nói chung thì nó sẽ so sánh giá trị first trước rồi mới đến giá trị second. Do đó ta để độ dài đường đi ở giá trị first vì khi đó đỉnh có dist[] nhỏ nhất sẽ được lấy ra trước. Code` include<bits/stdc++.h>using namespace std; typedef long long ll; const int MaxN = 1 + 1e2; const ll INF = 1e18; int n, m, s; bool mark[MaxN]; ll dist[MaxN]; vector<pair<int, int>> adj[MaxN]; void Dijkstra(int s){ }
int main(){ }
`Độ phức tạpKhi này, độ phức tạp của thuật toán sẽ giảm còn . Vấn đề kì sauĐể có thể chuẩn bị tốt hơn cho bài học kế tiếp, mình muốn đặt ra cho các bạn một câu hỏi: Ở đề bài mình nêu ở trên, các cạnh đều có trọng số không âm. Điều gì có thể sẽ xảy ra với thuật toán Dijkstra nếu các cạnh có trọng số âm? Kết luậnQua bài này chúng ta đã nắm về Tìm kiếm đường đi ngắn nhất trên đồ thị với thuật toán Dijkstra. Bài sau chúng ta sẽ tìm hiểu về Tìm kiếm đường đi ngắn nhất trên đồ thị với thuật toán Bellman-Ford. Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”. Tải xuốngTài liệuNhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Tìm kiếm đường đi ngắn nhất trên đồ thị (Dijikstra) dưới dạng file PDF trong link bên dưới. Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com Đừng quên like và share để ủng hộ Kteam và tác giả nhé! Thảo luậnNếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng. |