Bài giảng Toán rời rạc 2 - Chương 6: Bài toán tìm đường đi ngắn nhất
BÀI TOÁN TÌM ĐƯỜNG ĐI
NGẮN NHẤT
Toán rời rạc 2
Nội dung
• Phát biểu bài toán tìm đường đi ngắn nhất
• Thuật toán Dijkstra
• Thuật toán Bellman-Ford
• Thuật toán Floyd
2
Phát biểu bài toán tìm đường đi
ngắn nhất
Phát biểu bài toán
• Xét đồ thị G=<V, E>:
– Với mỗi cạnh (u, v)E, ta đặt tương ứng với nó một số thực
A[u][v] được gọi là trọng số của cạnh.
– Ta sẽ đặt A[u,v]= nếu (u, v)E. Nếu dãy v0, v1, . . . , vk là một
đường đi trên G thì độ dài của đường đi của nó là.
• Bài toán dạng tổng quát:
– Tìm đường đi ngắn nhất từ một đỉnh xuất phát sV (đỉnh nguồn)
đến đỉnh cuối tV (đỉnh đích).
– Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t.
– Độ dài của đường đi d(s,t) được gọi là khoảng cách ngắn nhất
từ s đến t (trong trường hợp tổng quát d(s,t) có thể âm).
– Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi
d(s,t)=.
4
Một số thể hiện cụ thể của bài toán
• Trường hợp 1. Nếu s cố định và t thay đổi:
– Tìm đường đi ngắn nhất từ s đến tất cả các đỉnh còn lại trên đồ
thị.
– Với đồ thị có trọng số không âm, bài toán luôn có lời giải bằng
thuật toán Dijkstra.
– Với đồ thị có trọng số âm nhưng không tồn tại chu trình âm, bài
toán có lời giải bằng thuật toán Bellman-Ford.
– Trường hợp đồ thị có chu trình âm, bài toán không có lời giải.
• Trường hợp 2. Nếu s thay đổi và t cũng thay đổi:
– Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị.
– Bài toán luôn có lời giải trên đồ thị không có chu trình âm.
– Với đồ thị có trọng số không âm, bài toán được giải quyết bằng
cách thực hiện lặp lại n lần thuật toán Dijkstra.
– Với đồ thị không có chu trình âm, bài toán có thể giải quyết bằng
thuật toán Floyd.
5
Thuật toán Dijkstra
Mô tả thuật toán
• Mục đích:
– Sử dụng để tìm đường đi ngắn nhất từ một đỉnh s tới các đỉnh
còn lại của đồ thị
– Áp dụng cho đồ thị có hướng với trọng số không âm.
• Tư tưởng:
– Gán nhãn tạm thời cho các đỉnh
– Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn
nhất tới đỉnh đó
– Các nhãn này sẽ được biến đổi (tính lại) nhờ một thủ tục lặp
– Ở mỗi một bước lặp sẽ có một nhãn tạm thời trở thành nhãn cố
định (nhãn đó chính là độ dài đường đi ngắn nhất từ s đến đỉnh
đó).
7
Thuật toán Dijkstra
8
Ví dụ 1- Dijkstra (1/2)
• Áp dụng thuật
toán Dijkstra tìm
đường đi ngắn
nhất từ đỉnh số 1
tới các đỉnh còn
lại của đồ thị.
9
Ví dụ 1 - Dijkstra (2/2)
10
Ví dụ 2 Dijkstra (1/3)
• Áp dụng thuật
toán Dijkstra
tìm đường đi
ngắn nhất từ
đỉnh số 1 tới
các đỉnh còn lại
của đồ thị được
biểu diễn dưới
dạng ma trận
trọng số như
hình bên.
11
Ví dụ 2 Dijkstra (2/3)
Các bước thực hiện thuật toán Dijkstra tại s =1
12
Ví dụ 2 Dijkstra (3/3)
• Kết quả:
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 2: 2. Đường đi: 1-2.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3: 4. Đường đi: 1-2-3.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4: 10. Đường đi: 1-2-3-4. Đường đi
ngắn nhất từ đỉnh 1 đến đỉnh 5: 8. Đường đi: 1-2-3-7-6-5.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6: 7. Đường đi: 1-2-3-7-6.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 7: 5. Đường đi: 1-2-3-7.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 8: 7. Đường đi: 1-2-3-7-8.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 9: 15. Đường đi: 1-2-3-7-6-9.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 10: 21. Đường đi: 1-2-3-7-6-9-10.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 11: 18. Đường đi: 1-2-3-7-8-12-13-11.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 12: 18. Đường đi: 1-2-3-7-8-12.
– Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 13: 11. Đường đi: 1-2-3-7-8-12-13.
13
Cài đặt thuật toán Dijkstra
• Xem code minh họa.
14
Thuật toán Bellman-Ford
Mô tả thuật toán
• Mục đích
– Sử dụng để tìm đường đi ngắn nhất từ một đỉnh s tới các đỉnh
còn lại của đồ thị
– Áp dụng cho đồ thị có hướng và không có chu trình âm (có thể
có cạnh âm)
• Tư tưởng
– Gán nhãn tạm thời cho các đỉnh
– Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn
nhất tới đỉnh đó
– Các nhãn này sẽ được làm tốt dần (tính lại) nhờ một thủ tục lặp
– Mỗi khi phát hiện d[v] > d[u] + A[u][v], cập nhật đ*v+= d[u]+A[u][v].
16
Thuật toán Bellman-Ford
17
Ví dụ 1: Bellman-Ford (1/2)
• Áp dụng thuật
toán Bellman-
Ford tìm đường
đi ngắn nhất từ
đỉnh số 1 tới
các đỉnh còn lại
của đồ thị.
18
Ví dụ 1: Bellman-Ford (2/2)
19
Ví dụ 2 Bellman-Ford (1/2)
• Áp dụng thuật
toán Bellman-
Ford tìm đường
đi ngắn nhất từ
đỉnh số 1 tới
các đỉnh còn lại
của đồ thị được
biểu diễn dưới
dạng ma trận
trọng số như
hình bên.
20
Tải về để xem bản đầy đủ
28 trang
24280
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 6: Bài toán tìm đường đi ngắn nhất", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_6_bai_toan_tim_duong_di_ngan.pdf
