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 - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Bài toán tìm đường đi ngắn nhất
Ngô Xuân Bách
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
Bài toán tìm đường đi ngắn nhất (1/2)
Khái niệm độ dài đường đi trên đồ thị
o Xét đồ thị 퐺 =< 푉, 퐸 > với tập đỉnh 푉 và tập cạnh 퐸
o Với mỗi cạnh (푢, 푣) ∈ 퐸, ta đặt tương ứng một số thực 푎(푢, 푣)
được gọi là trọng số của cạnh, 푎(푢, 푣) = ∞ nếu (푢, 푣) ∉ 퐸
푘
o Nếu dãy 푣0, 푣1, . . . , 푣푘 là một đường đi trên 퐺 thì 푖=1 푎(푣푖−1, 푣푖)
được gọi là độ dài của đường đi
Bài toán dạng tổng quát
o Tìm đường đi (có độ dài) ngắn nhất từ một đỉnh xuất phát 푠 ∈ 푉
(đỉnh nguồn) đến đỉnh cuối 푡 ∈ 푉 (đỉnh đích)?
o Đường đi như vậy được gọi là đường đi ngắn nhất từ 푠 đến 푡, độ
dài của đường đi 푑(푠, 푡) được gọi là khoảng cách ngắn nhất từ 푠
đến 푡
o Nếu không tồn tại đường đi từ 푠 đến 푡 thì độ dài đường đi
푑(푠, 푡) = ∞
3
Bài toán tìm đường đi ngắn nhất (2/2)
Trường hợp 1: 푠 cố định, 푡 thay đổi
o Tìm đường đi ngắn nhất từ 푠 đến tất cả các đỉnh còn lại trên đồ
thị ?
o Đối 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
o Đối 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
o Trong 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: 푠 thay đổi và 푡 cũng thay đổi
o Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị
o Đối 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 푛 lần thuật toán Dijkstra
o Đối 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
4
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
5
Thuật toán Dijkstra (1/2)
Mục đích
o Sử dụng để tìm đường đi ngắn nhất từ một đỉnh 푠 tới các đỉnh còn
lại của đồ thị
o Áp dụng cho đồ thị có hướng với trọng số không âm
Tư tưởng
o 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 đó
o 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ừ 푠 đến đỉnh đó)
6
Thuật toán Dijkstra (2/2)
Dijkstra (푠){
Bước 1 (Khởi tạo):
푑,푠- = 0; //Gán nhãn của đỉnh 푠 là 0
푇 = 푉\*푠+; // 푇 là tập đỉnh có nhãn tạm thời
for (푣 ∈ 푉){ //Sử dụng 푠 gán nhãn cho các đỉnh còn lại
푑,푣- = 푎(푠, 푣);
푡푟푢표푐,푣- = 푠;
}
Bước 2 (Lặp):
while (푇 ≠ ∅ ){
Tìm đỉnh 푢 ∈ 푇 sao cho 푑,푢- = min* 푑,푧- | 푧 ∈ 푇+;
푇 = 푇\*푢+; //cố định nhãn đỉnh 푢
for (푣 ∈ 푇){ //Sử dụng 푢, gán nhãn laị cho các đỉnh
if (푑,푣- > 푑,푢- + 푎(푢, 푣)){
푑,푣- = 푑,푢- + 푎(푢, 푣); //Gán lại nhãn cho đỉnh 푣;
푡푟푢표푐,푣- = 푢;
}
}
}
7
}
Ví dụ - 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ị.
7
2
3
6
1
5
1
1
1
2
4
5
1
4
2
3
8
Ví dụ - Dijkstra (2/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ị.
7
2
3
6
1
5
1
1
1
2
4
푑,푢-
푡푟푢표푐,푢-
5
1
4
2
3
Bước lặp Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 Đỉnh 6
Khởi tạo
0, 1
1, 1 *
∞, 1
6, 2
4, 4 *
-
∞, 1
∞, 1
∞, 1
7, 4
∞, 1
8, 2
8, 2
5, 3 *
-
1
2
3
4
5
-
-
-
-
-
-
-
-
3, 2 *
-
-
-
7, 4
-
6, 6 *
9
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
10
Thuật toán Bellman-Ford (1/2)
Mục đích
o Sử dụng để tìm đường đi ngắn nhất từ một đỉnh 푠 tới các đỉnh còn
lại của đồ thị
o Á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
o 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 đó
o 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 푑,푣- > 푑,푢- + 푎(푢, 푣), cập nhật 푑 푣 = 푑,푢- + 푎(푢, 푣)
11
Thuật toán Bellman-Ford (2/2)
Bellman-Ford(푠){
Bước 1 (Khởi tạo):
for (푣 ∈ 푉){ //Sử dụng 푠 gán nhãn cho các đỉnh còn lại
푑,푣- = 푎(푠, 푣);
푡푟푢표푐,푣- = 푠;
}
Bước 2 (Lặp):
푑 푠 = 0;
for (푘 = 1; 푘 ≤ 푛 − 2; 푘 + + ){
for (푣 ∈ 푉\*푠+){
for (푢 ∈ 푉){
if (푑,푣- > 푑,푢- + 푎(푢, 푣)){
푑,푣- = 푑,푢- + 푎(푢, 푣);
푡푟푢표푐,푣- = 푢;
}
}
}
}
}
12
Ví dụ: Bellman-Ford (1/2)
3
5
1
Á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ị.
8
1
4
-5
3
2
4
3
1
3
2
13
Ví dụ: Bellman-Ford (2/2)
3
5
1
Á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ị.
8
1
4
-5
3
2
4
3
1
3
푑,푢-
푡푟푢표푐,푢-
2
Bước lặp Đỉnh 1 Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5
Khởi tạo
0, 1
0, 1
0, 1
0, 1
1, 1
1, 1
1, 1
1, 1
∞, 1
4, 2
4, 2
4, 2
∞, 1
4, 2
3, 5
3, 5
3, 1
-1, 3
-1, 3
-1, 3
k=1
2
3
14
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
15
Thuật toán Floyd (1/3)
Mục đích
o Sử dụng để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của
đồ thị
o Á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
o 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
16
Thuật toán Floyd (2/3)
Floyd( ){
Bước 1 (Khởi tạo):
for (푖 = 1, 푖 ≤ 푛; 푖 + +){
for( 푗 = 1, 푗 ≤ 푛; 푗 + +){ //Xét từng cặp đỉnh
푑,푖, 푗- = 푎(푖, 푗);
푛푒푥푡,푖, 푗- = 푗;
}
}
Bước 2 (Lặp):
for (푘 = 1, 푘 ≤ 푛; 푘 + +){
for (푖 = 1, 푖 ≤ 푛; 푖 + +){
for (푖 = 푗, 푗 ≤ 푛; 푗 + +){
if (푑,푖, 푗- > 푑,푖, 푘- + 푑,푘, 푗-){
푑,푖, 푗- = 푑,푖, 푘- + 푑,푘, 푗-;
푛푒푥푡,푖, 푗- = 푛푒푥푡,푖, 푘-;
}
}
}
}
17
}
Thuật toán Floyd (3/3)
Khôi phục đường đi
Reconstruct-Path( 푢, 푣){
if ( 푛푒푥푡,푢-,푣- == 푛푢푙푙)
<Không có đường đi từ 푢 đến 푣>;
else{
푝푎푡ℎ = ,푢-; // path bắt đầu từ 푢
while(푢 ≠ 푣){
푢 = 푛푒푥푡,푢-,푣-;
푝푎푡ℎ. 푎푝푝푒푛푑(푢); //đỉnh tiếp theo trên đường đi
}
return 푝푎푡ℎ;
}
}
18
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ị.
1
-2
4
3
2
3
-1
2
4
19
Tóm tắt
Bài toán tìm đường đi ngắn nhất trên đồ thị, các dạng
của bài toán
Thuật toán Dijkstra, áp dụng
Thuật toán Bellman-Ford, áp dụng
Thuật toán Floyd, áp dụng
20
Tải về để xem bản đầy đủ
21 trang
27/04/2022
24860
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 - Ngô Xuân Bách", để 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
