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

Lượt xem: 144,429Lượt tải: 1Số trang: 10

Mô tả tài liệu

Tham khảo tài liệu 'đường đi ngằn nhất', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Tóm tắt nội dung

ĐưĐườờ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)