Bài tập tìm đường đi ngắn nhất có lời giải

home bài viết Phần 4: Đường đi ngắn độc nhất trên thứ thị với thuật toán Dijkstra
Phần 4: Đường đi ngắn duy nhất trên trang bị thị cùng thuật toán Dijkstra

Đăng do Phương Nguyễn thời điểm 09 Aug 2017


Phần trước: Phần 3: tra cứu kiếm theo chiều sâu trên thứ thị - Depth-First search (DFS)

Đường đi ngắn tốt nhất trên trang bị thị

Nếu vật dụng thị màn biểu diễn một mạng lưới giao thông, thì tín đồ ta không chỉ là quan chổ chính giữa tới việc có tồn tại con đường đi xuất phát từ 1 đỉnh này cho tới đỉnh khác tuyệt không, mà bạn ta còn nhiệt tình tới con đường tối ưu nhất, ngắn nhất có thể.

Bạn đang xem: Bài tập tìm đường đi ngắn nhất có lời giải

Trong kim chỉ nan đồ thị, bài toán lối đi ngắn tốt nhất giữa nhì đỉnh cho trước là câu hỏi tìm một đường đi giữa chúng làm sao cho tổng các trọng số của những cạnh khiến cho đường đi kia là nhỏ dại nhất. Định nghĩa một cách hình thức, đến trước một đồ vật thị bao gồm trọng số ( G = (V, E, w) ) (nghĩa là 1 trong những tập đỉnh V, một tập cạnh E, với một hàm trọng số có giá trị thực w : E → R), đến trước một đỉnh u nằm trong V, tra cứu một đường đi p. Từ u cho tới một đỉnh v ở trong V sao cho:

nhỏ duy nhất trong toàn bộ các lối đi từ u tới v. Bài xích toán lối đi ngắn độc nhất giữa phần nhiều cặp đỉnh là 1 bài toán tương tự, trong những số đó ta phải tìm những đường đi ngắn tuyệt nhất cho mọi cặp đỉnh u với v.

Các thuật toán thường xuyên được dùng để giải quyết những việc này là:

Thuật toán Dijkstra - giải câu hỏi bài toán đường đi ngắn duy nhất giữa nhị đỉnh đến trước nếu toàn bộ các trọng số số đông không âm. Thuật toán này có thể tính toán tất cả các đường đi ngắn nhất từ 1 đỉnh khởi thủy cho trước s tới phần nhiều đỉnh khác nhưng mà không làm cho tăng thời hạn chạy. Thuật toán Bellman-Ford - giải việc bài toán đường đi ngắn độc nhất giữa nhị đỉnh đến trước trong trường đúng theo trọng số có thể có quý giá âm. Giải mã tìm tìm A* giải bài toán bài toán lối đi ngắn tốt nhất giữa nhì đỉnh đến trước sử dụng heuristics nhằm tăng tốc độ tìm tìm Thuật toán Floyd-Warshall - giải bài toán đường đi ngắn độc nhất cho đều cặp đỉnh. Thuật toán Johnson - giải bài xích toán lối đi ngắn duy nhất cho hồ hết cặp đỉnh, rất có thể nhanh rộng thuật toán Floyd-Warshall trên các đồ thị thưa. Lý thuyết nhiễu (Perturbation theory) - tìm lối đi ngắn độc nhất địa phương (trong trường hợp xấu nhất)

Chú ý:

Ta bao gồm đường đi phường = v1, v2, …, vk là 1 trong những đường đi ngắn độc nhất vô nhị từ v1 cho tới vk. Lúc đó ta có nhận xét, đường đi từ vi tới vj qua vi, vi+1, …, vj cùng với i,j ∈ <1, k> là 1 trong những đường đi ngắn độc nhất từ vi cho tới vj.

Thuật toán Dijkstra

Trong ngôi trường hợp vật thị ( G = (V, E, w) ) bao gồm trọng số trên các cạnh ko âm, ta có thuật toán Dijkstra để tìm đường đi ngắn duy nhất từ đỉnh căn nguyên s tới các đỉnh khác của đồ dùng thị.

Xem thêm: Xem Phim Vượt Ngục ) (Hd,Thuyết Minh), Xem Phim Vượt Ngục

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

Ta tất cả mảng kc là khoảng cách ngắn tuyệt nhất từ đỉnh s cho tới đỉnh u trên đồ thị. Thuở đầu kc = 0, những giá trị khác bởi dương vô cực. Ta vẫn lấy đỉnh u bao gồm kc nhỏ nhất vào thời gian hiện tại, và sử dụng khoảng cách của nó để cập nhật khoảng bí quyết ngắn nhất của các đỉnh xung quanh. Với cùng một đỉnh u bất kì, vì nó được update bởi những đường đi ngắn nhất của các đỉnh bao phủ nó, nên bạn dạng thân lối đi của nó cũng chính là ngắn nhất.

*

Dữ liệu:

Đồ thị được màn trình diễn bằng list kề với cùng một mảng vector g cùng với g lưu những đỉnh kề của u hẳn nhiên trọng số Mảng kc dùng làm lưu trữ độ dài lối đi ngắn tốt nhất từ đỉnh nguồn s mang đến đỉnh u. Để tính được giá trị bé dại nhất này, lúc khởi chế tác ta phải gán mang lại kc = +∞ (khi cài bỏ lên trên máy tính, ta chỉ cần đặt bởi một quý hiếm cực lớn), sau đó chạm mặt giá trị bé dại hơn thì sửa chữa lại. đa số đỉnh đã tính được kc hữu hạn được cho vào một trong những hàng đợi tất cả ưu tiên. Hàng ngóng này luôn được bổ sung và thu xếp lại bằng một cấu tạo hợp lý (heap, set,…) Để theo dõi và quan sát trạng thái của những đỉnh trong quy trình xét, ta dùng hàm cl. Ban đầu các đỉnh được tô white color (cl=0), khi vẫn tính dứt khoảng cách nó được tô color đen(cl != 0). Nếu cần khắc ghi đường đi ta sẽ buộc phải dùng một hàm pre để chỉ đỉnh đứng tức thì trước đỉnh u trên tuyến đường đi ngắn tuyệt nhất từ s tới u.

Cài để bằng ngôn ngữ C++ sử dụng set:

#define fs first#define sc secondtypedef pairint,int> II;vectorII> g;setII> S;int cl, kc;void Dijkstra(int s) memset(kc,0,sizeof(kc));cl=1;S.insert(II(kc,s));while(!s.empty())II t=*S.begin();S.erase(t);int u=t.sc;for(int i=0; iS.size(); ++i)int v=g.fs, L=g.sc;if(cl==0)cl=1;kc=kc+L;S.insert(II(kc,v)); else if(kc>kc+L)S.erase(II(kc,v));kc=kc+L;S.insert(II(kc,v));

Độ phức tạp

Thuật toán Dijkstra bình thường sẽ bao gồm độ phức tạp là ( O(n^2+m) ), vị ta buộc phải duyệt n lần (đối với n đỉnh), mỗi lần duyệt lại bắt buộc duyệt qua n đỉnh để tìm đỉnh gồm kc bé dại nhất. Tuy vậy ta hoàn toàn có thể sử dụng phối hợp với cấu trúc heap hoặc set, lúc đó độ phức hợp sẽ là ( O((m+n)log(n)) ), nếu sử dụng Fibonacci thì độ phức tạp giảm xuống còn ( O(m+nlog n) ). Trong những số đó m là số cạnh, n là số đỉnh của thiết bị thị đã xét (giới thiệu ở bài xích sau).