Bài giảng Lý thuyết đồ thị: Chương 5 - Nguyễn Trần Phi Phượng
lượt xem 20
download
Bài giảng Lý thuyết đồ thị: Chương 5 - Bài toán đường đi ngắn nhất của Nguyễn Trần Phi Phương sau đây bao gồm những nội dung về đồ thị có trọng số - bài toán đường đi ngắn nhất; thuật toán Ford-Bellman; thuật toán Dijkstra; thuật toán Floyd – đường đi ngắn nhất giữa tất cả các cặp đỉnh.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 5 - Nguyễn Trần Phi Phượng
- Chương 5 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất Bài toán: Cho G = là đồ thị có trọng số. s và t là 2 đỉnh của đồ thị. Hãy tìm đường đi có tổng trọng số nhỏ nhất từ s đến t. 20 VD: 5 15 15 3 9 9 5 5 Đường đi ngắn nhất từ Etna đến Oldtown là: Etna – Bangor – Orono – OldTown Đường đi ngắn nhất từ Hermae đến Etna là: Hermae – Hampdea – Bangor - Etna 09/04/2011 Lý thuyết đồ thị 2
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất 1 10 2 5 7 20 9 -6 9 4 3 4 5 Tìm đường đi ngắn nhất từ đỉnh 3 đến đỉnh 5 – Trả lời: 3 – 1 – 2 – 5 ??? Độ dài 11 là ngắn nhất ??? – Đường đi này thì sao? Độ dài là bao nhiêu? 3–1–2–5–2–5 – Đường đi trên đã ngắn nhất chưa??? 09/04/2011 Lý thuyết đồ thị 3
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất Điều kiện để bài toán có lời giải: – Phải tồn tại đường đi từ s đến t: • Đồ thị vô hướng liên thông • Đồ thị có hướng liên thông mạnh • Đồ thị vô hướng, s và t nằm trong cùng một thành phần liên thông • Đồ thị có hướng, có tồn tại đường đi từ s đến t – Trong đồ thị không tồn tại chu trình âm 1 5 2 7 3 • Đồ thị có hướng: không tồn tại chu trình âm. ‐ 3 6 2 8 • Đồ thị vô hướng: không tồn tại cạnh âm. 4 1 5 6 09/04/2011 Lý thuyết đồ thị 4
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất Nhận xét: – Nếu v là đỉnh trung gian trên đường đi ngắn nhất từ s đến t thì đường đi từ s đến v phải là ngắn nhất và đường đi từ v đến t cũng phải là ngắn nhất. s … v t X … … – Do đó, để tối ưu, người ta mở rộng bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị. 09/04/2011 Lý thuyết đồ thị 5
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất – Dò tìm bằng cách thử đi qua các đỉnh trung gian – Nếu phát hiện đường đi qua đỉnh trung gian ngắn hơn đường đi hiện tại thì sẽ cập nhật đường đi mới, đồng thời chỉnh sửa các thông tin liên quan. – Sử dụng hai mảng để lưu trữ tạm thời: • Mảng d[v]: Lưu trữ độ dài đường đi ngắn nhất hiện tại từ s đến v. • Mảng T[v]: Lưu trữ đỉnh nằm trước v trên đường đi ngắn nhất hiện tại. 09/04/2011 Lý thuyết đồ thị 6
- 5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất Truoc[v] d[v] s X … v … c[u,v] d[u] u if (d[v] > d[u] + c[u,v]) { d[v] = d[u] + c[u,v]; Truoc[v] = u; } 09/04/2011 Lý thuyết đồ thị 7
- 5.2 Thuật toán Ford-Bellman //Khởi tạo for v ∈ V { d[v]=c[s,v]; Truoc[v]=s; } //Bắt đầu d[s]=0; k 1 2 3 4 5 for (k=1; k d[u] +c[u,v]) 1 0,1 1,1 4,2 4,2 -1,3 { 2 0,1 1,1 4,2 3,5 -1,3 d[v]=d[u]+c[u,v]; Truoc[v]=u; 3 0,1 1,1 4,2 3,5 -1,3 } 09/04/2011 Lý thuyết đồ thị 8
- 5.2 Thuật toán Ford-Bellman Cây kết quả: 1 2 3 k 1 2 3 4 5 5 0,1 1,1 ∞ ,1 ∞ ,1 3,1 1 0,1 1,1 4,2 4,2 -1,3 4 2 0,1 1,1 4,2 3,5 -1,3 3 0,1 1,1 4,2 3,5 -1,3 09/04/2011 Lý thuyết đồ thị 9
- 5.2 Thuật toán Ford-Bellman k 1 2 3 4 5 6 0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1 1 0,1 1,1 6 ,2 3 ,2 7,4 7,3 2 0,1 1,1 4 ,4 3 ,2 7,4 5,3 3 0,1 1,1 4 ,4 3 ,2 6,6 5,3 S=1 4 0,1 1,1 4 ,4 3 ,2 6,6 5,3 09/04/2011 Lý thuyết đồ thị 10
- 5.2 Thuật toán Ford-Bellman Cây kết quả 1 2 4 k 1 2 3 4 5 6 0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1 3 1 0,1 1,1 6 ,2 3 ,2 7,4 7,3 6 2 0,1 1,1 4 ,4 3 ,2 7,4 5,3 3 0,1 1,1 4 ,4 3 ,2 6,6 5,3 5 4 0,1 1,1 4 ,4 3 ,2 6,6 5,3 09/04/2011 Lý thuyết đồ thị 11
- 5.2 Thuật toán Ford-Bellman Nhận xét: – Áp dụng được cho mọi trường hợp – Chi phí tính toán lớn do dùng 3 vòng lặp lồng nhau – Thường lãng phí một số bước sau cùng Cải tiến: – Không thể cải tiến tốt hơn cho trường hợp tổng quát – Chỉ có thể làm tốt hơn cho một số trường hợp riêng 09/04/2011 Lý thuyết đồ thị 12
- 5.3 Thuật toán Dijkstra Nhận xét về Ford-Bellman: k 1 2 3 4 5 6 0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1 1 0,1 1,1 6 ,2 3 ,2 7,4 7,3 2 0,1 1,1 4 ,4 3 ,2 7,4 5,3 3 0,1 1,1 4 ,4 3 ,2 6,6 5,3 4 0,1 1,1 4 ,4 3 ,2 6,6 5,3 – Kết quả của bảng đã ổn định từ sớm – Trên một dòng, giá trị d nhỏ nhất không thay đổi về sau nếu trọng số các cạnh là không âm 09/04/2011 Lý thuyết đồ thị 13
- 5.3 Thuật toán Dijkstra Chú ý: thuật toán này chỉ dùng cho đồ thị không có cạnh âm. Ý tưởng: – Do không có cạnh âm nên tại mỗi bước, sẽ có một đỉnh mà thông tin về nó sẽ không thay đổi về sau – Tại mỗi bước, ta không cần phải kiểm tra qua tất cả các đỉnh trung gian, mà chỉ thực hiện như sau: • Chọn một đỉnh u có giá trị d[u] nhỏ nhất • Chọn u làm đỉnh trung gian để xác định các bước kế tiếp 09/04/2011 Lý thuyết đồ thị 14
- 5.3 Thuật toán Dijkstra //Khởi tạo for v ∈ V { d[v]=c[s,v]; Truoc[v]=s; } d[s]=0; T=V\{s} ; //T là tập các đỉnh chưa cố định //Bước lặp while T != ∅ { k 1 2 3 4 5 6 Tìm đỉnh u ∈ T thoả mãn d[u]=min{d[z]:z∈T}; T=T\{u} ; //Cố định nhãn của đỉnh u 0,1 1,1* ∞,1 ∞,1 ∞,1 ∞,1 For v∈ T If d[v]>d[u]+c[u,v] then 1 6,2 3,2* ∞,1 8,2 { d[v]=d[u]+c[u,v]; 2 4,4* 7,4 8,2 Truoc[v]=u; } 3 7,4 5,3* } 4 6,6* 09/04/2011 Lý thuyết đồ thị 15
- 5.3 Thuật toán Dijkstra Cây kết quả 1 2 4 k 1 2 3 4 5 6 0,1 1,1* ∞,1 ∞,1 ∞,1 ∞,1 3 1 6,2 3,2* ∞,1 8,2 6 2 4,4* 7,4 8,2 5 3 7,4 5,3* 4 6,6* 09/04/2011 Lý thuyết đồ thị 16
- 5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa tất cả các cặp đỉnh Thuật toán Floyd – Đầu vào: Ma trận kề trọng số A – Đầu ra: • Ma trận đường đi ngắn nhất: d • Ma trận lưu đỉnh trước đó trên đường đi: p 09/04/2011 Lý thuyết đồ thị 17
- 5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa tất cả các cặp đỉnh // Khởi tạo 1 10 2 For (i=1; i
- 5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa tất cả các cặp đỉnh 10 ⎡ ∞ 10 6 2 ⎤ ⎡1 1 1 1 ⎤ 1 2 ⎢10 ∞ 5 3 ⎥ ⎢2 2 2 2⎥ 3 Khởi ⎢ ⎥ ⎢ ⎥ 6 ⎢ 6 5 ∞ 1⎥ ⎢3 3 3 3⎥ 2 5 tạo ⎢ ⎥ ⎢ ⎥ ⎣ 2 3 1 ∞ ⎦ ⎣ 4 4 4 4 ⎦ 1 4 3 Ma trận d Ma trận p ⎡ ∞ 10 6 2 ⎤ ⎡1 1 1 1⎤ ⎡ ∞ 10 6 2 ⎤ ⎡1 1 1 1⎤ ⎢10 ∞ 5 3 ⎥ ⎢2 2 2 2 ⎥⎥ ⎢10 ∞ 5 3 ⎥ ⎢2 2 2 2 ⎥⎥ k=3 k=1 ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎢ 6 5 ∞ 1⎥ ⎢3 3 3 3⎥ ⎢ 6 5 ∞ 1⎥ ⎢3 3 3 3⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 2 3 1 ∞ ⎦ ⎣4 4 4 4⎦ ⎣ 2 3 1 ∞ ⎦ ⎣4 4 4 4⎦ ⎡ ∞ 10 6 2 ⎤ ⎡1 1 1 1⎤ ⎡∞ 5 3 2 ⎤ ⎡1 4 4 1⎤ ⎢10 ∞ 5 3 ⎥ ⎢2 2 2 2 ⎥⎥ ⎢5 ∞ 4 3⎥ ⎢4 2 4 2 ⎥⎥ k=4 k=2 ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ ⎢ 6 5 ∞ 1⎥ ⎢3 3 3 3⎥ ⎢3 4 ∞ 1⎥ ⎢4 4 3 3⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 2 3 1 ∞ ⎦ ⎣4 4 4 4⎦ ⎣ 2 3 1 ∞ ⎦ ⎣4 4 4 4⎦ 09/04/2011 Lý thuyết đồ thị 19
- 5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa tất cả các cặp đỉnh 1 10 2 ⎡∞ 5 3 2 ⎤ ⎡1 4 4 1⎤ 3 ⎢5 ∞ 4 3⎥ ⎢4 2 4 2 ⎥⎥ 2 6 5 ⎢ ⎥ ⎢ ⎢3 4 ∞ 1⎥ ⎢4 4 3 3⎥ 4 1 3 ⎢ ⎥ ⎢ ⎥ ⎣ 2 3 1 ∞⎦ ⎣4 4 4 4⎦ – Từ 1 đến 3: • Trước 3 là p[1,3] = 4. Vậy 4 là đỉnh nằm trước 3 trên đường đi này. • Trước 4 là p[1,4] = 1. Vậy 1 là đỉnh nằm trước 4 trên đường đi này. • Dừng. Đường đi là: 1 – 4 – 3 với độ dài là d[1,3] = 3 – Tương tự, đường đi ngắn nhất từ 3 đến 2 là: 3 – 4 – 2 với độ dài là p[3,2] = 4 09/04/2011 Lý thuyết đồ thị 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết đồ thị: Chương 4 - Đồ thị phẳng – Bài toán tô màu đồ thị
21 p | 215 | 28
-
Bài giảng Lý thuyết đồ thị: Chương 1 - ThS. Nguyễn Khắc Quốc
56 p | 142 | 18
-
Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton
19 p | 148 | 16
-
Bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính
32 p | 119 | 16
-
Bài giảng Lý thuyết đồ thị: Chương 4 - ThS. Nguyễn Khắc Quốc
36 p | 120 | 14
-
Bài giảng Lý thuyết đồ thị: Chương 3 - ThS. Nguyễn Khắc Quốc
67 p | 114 | 13
-
Bài giảng Lý thuyết đồ thị: Chương 5 - Cây và cây khung của đồ thị
37 p | 177 | 12
-
Bài giảng Lý thuyết đồ thị: Chương 2 - ThS. Nguyễn Khắc Quốc
37 p | 115 | 12
-
Bài giảng Lý thuyết đồ thị: Chương 5 - ThS. Nguyễn Khắc Quốc
55 p | 109 | 8
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học
12 p | 102 | 7
-
Bài giảng Lý thuyết đồ thị: Chương 1 - Nguyễn Trần Phi Phượng
26 p | 186 | 7
-
Bài giảng Lý thuyết đồ thị: Bài toán ghép cặp
43 p | 139 | 6
-
Bài giảng Lý thuyết đồ thị - ĐH Hàng Hải
35 p | 96 | 6
-
Bài giảng Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị
39 p | 39 | 5
-
Bài giảng Lý thuyết đồ thị - Bài 3: Đường đi, chu trình Hamilton
34 p | 75 | 5
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Nguyễn Trần Phi Phượng
6 p | 93 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 4 - Nguyễn Trần Phi Phượng
13 p | 120 | 4
-
Bài giảng Lý thuyết đồ thị: Chương 0 - Tôn Quang Toại
6 p | 7 | 4
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn