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ớ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 s V (đỉnh nguồn) 
đến đỉnh cuối t V (đỉ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)
12
Các bước thực hiện thuật toán Dijkstra tại s =1
Ví dụ 2 Dijkstra (3/3)
13
• 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.
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
Ví dụ 2 Bellman-Ford (2/2)
21
Kết quả kiểm nghiệm theo thuật toán Bellman-Ford
Cài đặt thuật toán Bellman-Ford
• Xem code minh họa.
22
Thuật toán Floyd
Mô tả thuật toán
• Mục đích
– Sử dụng để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh 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
– Thực hiện quá trình lặp
• Xét từng đỉnh, với tất cả các đường đi (giữa 2 đỉnh bất kỳ), nếu đường đi 
hiện tại lớn hơn đường đi qua đỉnh đang xét, ta thay lại thành đường đi qua 
đỉnh này.
24
Thuật toán Floyd
25
Kiểm nghiệm thuật toán
• Áp dụng thuật 
toán Floyd 
tìm đường đi 
ngắn nhất 
giữa tất cả 
các cặp đỉnh 
của đồ thị.
26
Cài đặt thuật toán Floyd
• Xem code minh họa.
27
Bài tập
• Làm các bài tập 1, 5, 6 trong Tài liệu giảng dạy 
môn Toán rời rạc 2.
28