
ĐƯỜNG ĐI NGẰN NHẤT
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)