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
58822
Free
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
