ĐƯỜNG ĐI NGẰN NHẤT

ĐưĐườờng đi ngng đi ngắắn nhn thiệu: Bài toán tìm đường đi ngắn nhất là bài toán quan trọng trong lý thuyết đồ thi. Được ứng dụng trong thực tế: Giao thông, viễn toán chia làm 2 loại: � Tìm đường đi ngắn nhất giữa 1 cặp đỉnh: Cho 2 đỉnh u,v thuộc G, tìm đường đi ngắn nhất từ u đến v : Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh: Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v, với mọi cặp đỉnh u,v thuộc G: thui thuậật Dijkstrat thiệu: - Giải thuật Dijkstra giải bài toán đường đi ngắn nhất nguồn đơn (Single Source Shortest Path) trên một đồ thị có trọng số cạnh đều không âm. - Xác định đường đi ngắn nhất giữa 2 đỉnh a,b cho vấn đề: Ứng dụng giải thuật cây bao trùm tối thiểu để giải quyết bài toán đường đi ngắn nhất có được thui thuậật Dt xét: - Giải thuật để giải bài toán MST sẽ không ứng dụng được cho bài toán đường đi ngắn nhất. - Vì sao?? - Vì vậy cần phải chỉnh sửa giải thuật trên để phù hợp với bài toán đường đi ngắn thui thuậật Dt thuật: - Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: kv = 0 hoặc 1 – xác định trạng thái của đỉnh v ( 0 – chưa chọn, 1 – đã chọn) • dv: Chiều dài đường đi tìm thấy tại thời điểm đang xét từ a đến v • pv: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a � b. Đường đi ngắn nhất từ a đến b có dạng thui thuậật Dt Khởi tạo: dv= ∞,∀v ∈ V \{a}; da=0. B2: Chọn v∈V sao cho kv=0 và dv = min {dt / t∈V,kt=0 } – Nếu dv = ∞ thì kết thúc, không tồn tại đường đi từ a � b. B3: Đánh dấu đỉnh v, kv= 1. B4: Nếu v=b thì kết thúc và db là độ dài đường đi ngắn nhất từ a � b. Ngược lại nếu v ≠ b sang B5. B5: Với mỗi đỉnh u kề với v mà ku = 0, kiểm tra Nếu du > dv + w(v,u) thì du= dv + w(v,u) Ghi nhớ đỉnh v: pu:= v. Quay lại thui thuậật Dt dụ: Tìm đường đi ngắn nhất từ A� Tập hợp A thui thuậật Dt Hình bên là cây đường đi ngắn nhất từ đỉnh A đến các đỉnh - Với ví dụ: A�G, giải thuật sẽ kết thúc nếu tìm thấy đỉnh G thui thuậật Dt cây đường đi ngắn nhất từ đỉnh C đến các đỉnh còn lại của đồ thị thui thuậật Dt phức tạp của thuật toán: - Bình thường thuật toán Dijkstra có độ phức tạp Nếu sử dụng cấu trúc heap � thui thuậật Floydt toán: Tìm đường đi ngắn nhất của mỗi cặp đỉnh trong đồ thị Source Shortest Path)