Bài giảng Toán rời rạc 2 - Chương 4: Bài toán tìm đường đi ngắn nhất
CHꢀƠNG 4. BÀI TOÁN TÌM ĐꢀꢁNG ĐI NGꢂN NHꢃT
4.1 Đꢄꢅng đi ngꢆn nhꢇt xuꢇt phát từ 1 đỉnh
4.1.1 Thuꢈt toán Dijkstra
1) Đặt bài toán:
Input: Đồ thị G gồm n đỉnh cho bởi ma trận trọng số a với các phần tử 0, trong đó
a[i][j]= max nếu không có cạnh nối i với j; Đỉnh s;
Output: Độ dài d[v] đường đi từ s đến v và pr[v] là đỉnh trước v trên đường đi từ s đến
v.
1
2) Mô tꢉ thuꢈt toán
Khởi tạo: d[v]= a[s][v]; pr[v]= s; vs[v]= 0;
(1) Bắt đầu tìm kiếm từ s: d[s]= 0; pr[s]= 0; vs[s]= 1;
(2) Tìm đỉnh u sao cho d[u]= min{d[i] | vs[i] = 0}.
Nếu không tìm được thì chuyển sang (5). Nếu tìm được thì sang (3).
(3) Đặt vs[u]= 1.
(4) Đối với tất cả v G thỏa mãn (vs[v]= 0) & (d[v]> d[u] + a[u][v]) thì thay thế:
pr[v]= u; d[v]= d[u] + a[u][i]; và quay lại (2).
(5) Xuất d[v] và pr[v].
2
3) Kiểm nghiệm thuꢈt toán
Ví dụ: Cho đồ thị có trọng số G như hìmh bên.
Tìm đường đi ngắn nhất xuất phát từ
đỉnh a.
3
Giꢉi: Lần lượt có:
i
a
B
c
d
e
1
2
3
4
5
0; 0
2; a
2; a
9; a
3; b
3; b
m; a
6; b
6; b
6; b
10; a
10; a
10; a
8; d
8; d
Kết quꢉ: Độ dài đường đi ngắn nhất từ a đến b là 2: a b.
Độ dài đường đi ngắn nhất từ a đến c là 3: a b c.
Độ dài đường đi ngắn nhất từ a đến d là 6: a b d.
Độ dài đường đi ngắn nhất từ a đến e là 8: a b d e.
4
Ghi chú: Trong thực tế thường sử dụng giải thuật trên vào bài toán sau:
Input: Đồ thị G gồm n đỉnh cho bởi ma trận trọng số a với các phần tử 0, trong đó
a[i, j]= max nếu không có cạnh nối i với j; Hai đỉnh s và t;
Output: Độ dài d[t] đường đi từ s đến t và đường đi từ s đến t.
5
Giꢉi thuꢈt:
Khởi tạo: d[i]= a[s, i]; pr[i]= s; vs[i]= 0;
(1) Bắt đầu tìm kiếm từ s: d[s]= 0; pr[s]= 0; vs[s]= 1;
(2) Tìm đỉnh u sao cho d[u]= min{d[i] | vs[i] = 0}. Nếu không tìm được thì chuyển
sang (5). Nếu tìm được thì sang (3).
(3) Đặt vs[u]= 1. Nếu u= t thì chuyển sang (5); ngược lại chuyển sang (4);
(4) Đối với tất cả i G thỏa mãn (vs[i]= 0) & (d[i]> d[u] + a[u,v]) thì thay thế:
pr[i]= u; d[i]= d[u] + a[u, i]; và quay lại (2).
(5) Nếu d[t] < max thì xuất d[t] và đường đi từ s đến t; nếu ngược lại xuất không có
đường đi từ s đến t.
6
V́ ḍ. Cho đồ thị G = (V,E), với V = {1, 2, 3, 4, 5} biểu dĩn bởi hình ṽ sau, tìm
đường đi ngắn nhất từ đỉnh 1 đến đỉnh 2
Kết quꢉ: đường đi ngắn nhất là
1 3 2 và độ dài là 4.
7
4) Độ phức tạp tính toán
Giải thuật Dijkstra có độ phức tạp O(n2).
8
4.1.2 Thuꢈt toán Bellman-Ford
1) Đặt bài toán:
Input: Đồ thị G gồm n đỉnh cho bởi ma trận trọng số a không chứa chu trình âm, trong
đó a[i][j]= max nếu không có cạnh nối i với j; Đỉnh s;
Output: Độ dài d[v] đường đi từ s đến v và pr[v] là đỉnh trước v trên đường đi từ s đến
v.
9
2) Mô tꢉ thuꢈt toán
Khởi tạo: d[v]= a[s][v]; pr[v]= s; vs[v]= 0;
(1) Bắt đầu tìm kiếm từ s: d[s]= 0; pr[s]= 0; vs[s]= 1;
(2) Thực hiện n-2 lần lặp:
(2.1) Với mọi đỉnh v V\{s} thực hiện
(2.2)
Với mọi đỉnh u V thực hiện
Nếu d[v]> d[u] + a[u][v] thì thay thế:
pr[v]= u; d[v]= d[u] + a[u][i];
(3) Xuất d[v] và pr[v].
10
3) Kiểm nghiệm thuꢈt toán
Ví dụ: Cho đồ thị có trọng số G như hìmh bên.
Tìm đường đi ngắn nhất xuất phát từ
đỉnh a.
11
Giꢉi: Lần lượt có:
k
0
1
2
3
4
a
B
c
d
e
0; 0
2; a
2; a
2; a
2; a
2; a
9; a
3; b
3; b
3; b
3; b
∞; a
6; b
6; b
6; b
6; b
10; a
8; a
8; a
8; a
8; a
Kết quꢉ: Độ dài đường đi ngắn nhất từ a đến b là 2: a b.
Độ dài đường đi ngắn nhất từ a đến c là 3: a b c.
Độ dài đường đi ngắn nhất từ a đến d là 6: a b d.
Độ dài đường đi ngắn nhất từ a đến e là 8: a b d e.
12
4) Độ phức tạp tính toán
Thuật toán Bellman-ford có độ phức tạp O(n3).
13
4.2 Đꢄꢅng đi ngꢆn nhꢇt giữa các cặp đỉnh
1) Đặt bài toán
Input: Đồ thị G gồm n đỉnh cho bởi ma trận trọng số a với các phần tử 0, trong đó
a[i][j]= max nếu không có cạnh nối i với j;
Output: Độ dài d[i][j] đường đi từ i đến j và pr[i][j] là đỉnh trước j trên đường đi từ i
đến j.
14
2) Giꢉi thuꢈt Floyd
- Khởi tạo: d[i][j]= a[i][j]; pr[i][j]= i;
- Với mọi k G, i G, j G sao cho (d[i][j]> d[i][k] + d[k][j]) thì thay thế:
pr[i][j]= k; d[i][j]= d[i][k] + d[k][j];
- Xuất d[i][j] và pr[i][j].
15
3) Độ phức tạp tính toán
Thuật toán floyd có độ phức tạp O(n3).
16
16 trang
31900
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc 2 - Chương 4: 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_4_bai_toan_tim_duong_di_ngan.pdf
