Các thuật toán tìm đường đi ngắn nhất

khóa đào tạo Lập trình thiết kế C++ kết cấu dữ liệu và lời giải Tìm kiếm đường đi ngắn duy nhất trên đồ vật thị (Dijikstra)

Dẫn nhập

Trong bài học trước, họ đã thuộc nhau đi kiếm hiểu về thuật toán Floyd-Warshall trong tìm kiếm kiếm đường đi ngắn nhất trên đồ dùng thị. Hôm nay, bọn họ sẽ thuộc nhau đi tìm kiếm hiểu về một thuật toán rất có thể coi là thuật toán thông dụng nhất trong search kiếm đường đi ngắn nhất. Để biết cố gắng thể, hãy thuộc nhau bước đầu bài học tập nào!

Nội dung

Để hoàn toàn có thể tiếp thu bài học kinh nghiệm này một cách giỏi nhất, chúng ta nên gồm những kiến thức cơ bạn dạng về:

Trong bài học kinh nghiệm ngày hôm nay, bọn họ sẽ thuộc nhau tìm hiểu về:

Thuật toán Dijkstra

Thuật toán Dijkstra

Bài toán đặt ra

Ta tất cả một việc như sau:

Cho một đồ thị có hướng gồm

đỉnh (đánh số từ là một đến),

cạnh có hướng và gồm trọng số là số nguyên không âm. Cho một đỉnh, hãy tra cứu độ dài lối đi ngắn tốt nhất từ đỉnhđến toàn bộ các đỉnh còn lại. Nếu không tồn tại lối đi giữa hai đỉnh, in ra -1.

Bạn đang xem: Các thuật toán tìm đường đi ngắn nhất

Input:

Dòng : gồm 3 số nguyênlần lượt biểu hiện cho số đỉnh của đồ gia dụng thị, số cạnh của đồ thị và đỉnh yêu cầuDòng : từng dòng bao gồm 3 số nguyênthể hiện tại một cạnh được bố trí theo hướng nối từ đỉnhđến đỉnhvà tất cả trọng số

Output:

Gồm dòng, cái thứthể hiện độ dài đường đi ngắn duy nhất từ đỉnhđến đỉnh

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 đam mê ví dụ:

Đây là đồ dùng thị minh hoạ mang đến ví dụ trên

Ý tưởng

Ý tưởng của Dijkstra về cơ phiên bản khá kiểu như với thuật toán Floyd. Với cùng 1 cạnh nối liền hai đỉnh

và, ta sẽ so sánh độ dài lối đi trước đâyvới đường.

Tại từng bước, ta sẽ lựa chọn ra một đỉnh

mà ta biết chắc chắn là đường đi từlà đường đi ngắn nhất. Sau đó, ta vẫn xét tất cả các đỉnhmà bao gồm cạnh links trực tiếprồi về tối ưu đường đidựa trên phố đi.

Cách cài đặt

Trước hết, để diễn tả một cạnh, ta vẫn sử dụng những vector với hình trạng dữ liệupair. Pair là một cấu tạo cho phép ta lưu trữ hai phần tử. Ta rất có thể truy cập vào 2 thành phần củapair thông qua hai phương thứcfirst cùng second.

Ví dụ:

#includeusing namespace std;int main(){ pair myPair<2>; // có 2 phương pháp khởi tạo nên pair myPair<0> = make_pair(1, 2); myPair<1> = 2, 3; cout Ta sẽ nên khởi tạo ra hai mảng với ý nghĩa như sau:

dist: độ dài đường đi ngắn độc nhất từ đỉnh nguồns đến đỉnh u. Lúc đầu dist = ∞ với mọiu, riêng biệt dist = 0 mark: lưu lại đỉnhu đã được xét giỏi chưa. Ban sơ các phần tử trong mảng có giá trịfalse

Lưu ý: Trong laptop không tồn tại định nghĩa ∞ (vô cùng). Bởi đó, mỗi lúc viết ∞, ta sẽ hiểu đây là một quý giá đủ to để to hơn giá trị béo nhất rất có thể của mảng đó.

cạnh, mỗi cạnh tất cả trọng số không quá

nên độ lâu năm một đường đi không quá

. Giá bán trị

khi này rất có thể là bất kể giá trị nào lớn hơn hoặc bằng

.

Thuật toán sẽ diễn ra như sau:

Chọn một đỉnh u thế nào cho mark = false cùng dist bé dại nhấtVới đỉnh u nhưng mà ta đã chọn ở trên, ta sẽ xét các đỉnhv gồm cạnh nối trực tiếp từ u. Nếudist + (độ lâu năm cạnh u-v) lúc xét ngừng tất cả các đỉnh bao gồm cạnh nối trực tiếp từu, khắc ghi mark = true tức là đỉnhu đã xử trí xong.

Minh hoạ

Mình vẫn minh họa thuật toán bằng một trang bị thị cơ bạn dạng sau với đỉnh nguồn là đỉnh 1:

Đầu tiên, dist = <0, ∞, ∞, ∞> vàmark = <0, 0, 0, 0> (ta coi 0 là false và 1 là true).Ta lựa chọn u = 1 vì dist<1> = 0 nhỏ nhất cùng thoả mãn mark<1> = 0. Xét những đỉnhv bao gồm cạnh nối thẳng từ đỉnh 1.Xét v = 2, ta thấy dist<1> + độ nhiều năm cạnh (1, 2) = 3 Xét v = 3, ta thấy dist<1> + độ nhiều năm cạnh (1, 3) = 6 Do không thể đỉnh nối trường đoản cú đỉnh 1 đề xuất ta xong xét đỉnh 1 cùng đánh dấumark<1> = 1 lúc này, dist = <0, 3, 6, ∞> vàmark = <1, 0, 0, 0> Ta chọn u = 2 vày dist<2> = 3 nhỏ tuổi nhất cùng thoả mãn mark<2> = 0. Xét các đỉnhv tất cả cạnh nối trực tiếp từ đỉnh 2.Xét v = 3, ta thấy dist<2> + độ nhiều năm cạnh (2, 3) = 4 Xét v = 4, ta thấy dist<2> + độ dài cạnh (2, 4) = 10 Do không còn đỉnh nối từ đỉnh 2 phải ta xong xuôi xét đỉnh 2 với đánh dấumark<2> = 1 lúc này, dist = <0, 3, 4, 10> vàmark = <1, 1, 0, 0> Ta chọn u = 3 bởi dist<3> = 4 nhỏ tuổi nhất với thoả mãn mark<3> = 0. Xét các đỉnhv tất cả cạnh nối trực tiếp từ đỉnh 3.Xét v = 4, ta thấy dist<3> + độ lâu năm cạnh (3, 4) = 8 Do không thể đỉnh nối tự đỉnh 3 yêu cầu ta hoàn thành xét đỉnh 3 với đánh dấumark<3> = 1 khi này, dist = <0, 3, 4, 8> vàmark = <1, 1, 1, 0> Ta lựa chọn u = 4 do dist<4> = 0 bé dại nhất cùng thoả mãn mark<4> = 0. Xét các đỉnhv tất cả cạnh nối thẳng từ đỉnh 4.Do không hề đỉnh nối tự đỉnh 4 nên ta xong xét đỉnh 4 với đánh dấumark<4> = 1 Do toàn bộ các đỉnh vẫn được ghi lại nên thuật toán dứt và ta thu đượcdist = <0, 3, 4, 8>

Code cơ bản

Code

#includeusing namespace std;typedef long long ll;const int MaxN = 1 + 1e2;const ll INF = 1e18;int n, m, s;bool mark;ll dist;vector> adj;void Dijkstra(int s) fill(dist + 1, dist + n + 1, INF); dist = 0; for(int i = 1 ; i > n >> m >> s; for(int i = 0 ; i > u >> v >> w; adj.push_back(v, w); Dijkstra(s); for(int i = 1 ; i Độ phức tạpTa thấy trong khúc code trên, ta có một vòng lặp bên cạnh cùng tất 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 đầu tiên để tìm thấy đỉnh códist nhỏ dại nhất đang mất độ phức tạp

. Tuy nhiên, vòng lặp đồ vật hai nhằm tìm các đỉnh tất cả cạnh kề cùng với đỉnhu sẽ chỉ mất

trongcả bài bác toán. Lí do bởi vì mỗi cạnh vẫn chỉ được chu đáo qua nhất 1 lần.

Do đó, độ phức tạp tổng thể của công tác là

.

Xem thêm: Hướng Dẫn Sử Dụng Hàm Sumif Trong Excel: Cách Sử Dụng Và Ví Dụ Cụ Thể

Code cải tiến

Ý tưởng

Ta thấy với độ phức hợp trên thì bài toán vẫn không được giải quyết và xử lý trọn vẹn và giải mã sẽ cần được tối ưu thêm. Hiện thời hãy thuộc xem xét các yếu tố hoàn toàn có thể tối ưu được của bài toán.

Vòng lặp dùng để làm duyệt cùng xét tất cả các cạnh sẽ luôn phải xảy ra. Vì chưng đó, vòng lặp này sẽ không thể về tối ưu thêm nữa.

Ta vẫn xét đến vòng lặp dùng để tìm ra đỉnh u códist nhỏ tuổi 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 kinh nghiệm trước, bản thân đã trình làng cho chúng ta về một cấu trúc dữ liệu rất có thể tìm ra phần tử nhỏ tuổi nhất nhanh chóng. Chúng ta có còn nhớ nó không? Nó đó là priority_queueđó.

Ta sẽ sử dụng priority_queuelưu trữ những pair, trong số đó giá trịfirst là độ dài lối đi ngắn duy nhất từ đỉnh s mang đến đỉnhu, quý hiếm second là đỉnh u. Khipriority_queue đối chiếu cácpair nói thông thường thì nó sẽ đối chiếu giá trịfirst trước rồi new đến giá trị second. Vì thế ta nhằm độ dài lối đi ở giá trịfirst vì lúc đó đỉnh gồm dist<> nhỏ dại nhất đã được mang ra trước.

Code

#includeusing namespace std;typedef long long ll;const int MaxN = 1 + 1e2;const ll INF = 1e18;int n, m, s;bool mark;ll dist;vector> adj;void Dijkstra(int s) fill(dist + 1, dist + n + 1, INF); dist = 0; priority_queue, vector>, greater>> pq; pq.push(0, s); while(!pq.empty()) int u = pq.top().second; pq.pop(); if(mark) continue; mark = true; for(auto e : adj) int v = e.first; ll w = e.second; if(dist > dist + w) dist = dist + w; pq.push(dist, v); int main() freopen("CTDL.inp","r",stdin); freopen("CTDL.out","w",stdout); cin >> n >> m >> s; for(int i = 0 ; i > u >> v >> w; adj.push_back(v, w); Dijkstra(s); for(int i = 1 ; i Độ phức tạpKhi này, độ phức hợp của thuật toán sẽ sút còn

.

Vấn đề kì sau

Để tất cả thể chuẩn bị tốt hơn cho bài học kinh nghiệm 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 sinh sống trên, các cạnh đều phải sở hữu trọng số không âm. Điều gì rất có thể sẽ xảy ra với thuật toán Dijkstra nếu các cạnh bao gồm trọng số âm?

Kết luận

Qua bài bác này chúng ta đã thế về Tìm kiếm đường đi ngắn độc nhất trên đồ thịvới thuật toán Dijkstra.

Bài sau chúng ta sẽ tò mò về Tìm kiếm đường đi ngắn nhất trên vật 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 comment hoặc góp ý của bản thân để phát triển nội dung bài viết tốt hơn. Đừng quên “Luyện tập – thách thức – không lo khó”.

Thảo luận

Nếu bạn có bất kỳ khó khăn hay vướng mắc gì về khóa học, đừng ngần ngại đặt thắc mắc trong phần BÌNH LUẬN bên dưới hoặc vào mục HỎI và ĐÁP trên tủ sách kemhamysophie.com.com để nhận ra sự cung cấp từ cộng đồng.