Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất - Nguyễn Trần Phi Phượng

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất - Nguyễn Trần Phi Phượng

1. Chương 5 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT
2. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhất ƒBài toán: Cho G = là đồ thị có trọng số.svàtlà 2 đỉnh của đồ thị. Hãy tìm đường đicótổng trọng số nhỏ nhấttừ s đếnt. 20 VD: 5 15 15 3 9 9 5 5 ƒ Đường đingắnnhấttừ Etna đến Oldtown là: Etna – Bangor – Orono – OldTown ƒ Đường đingắnnhấttừ Hermae đến Etna là: Hermae – Hampdea – Bangor - Etna 09/04/2011 Lý thuyết đồ thị 2
3. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhất 1 10 2 5 7 20 9 -6 9 4 3 4 5 Tìm đường đingắnnhấttừđỉnh 3 đến đỉnh 5 –Trả lời:3–1–2–5???Độ dài 11 là ngắnnhất ??? – Đường đi này thì sao? Độ dài là bao nhiêu? 3 –1 –2 –5 –2 –5 – Đường đi trên đãngắnnhấtchưa??? 09/04/2011 Lý thuyết đồ thị 3
4. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhất Điềukiện để bài toán có lờigiải: –Phảitồntại đường đitừ s đếnt: • Đồ 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ồntại đường đitừ s đếnt – Trong đồ thị không tồntại chu trình âm 1 5 2 7 3 • Đồ thị có hướng: không tồntại chu trình âm. ‐ 3 6 2 8 • Đồ thị vô hướng: không tồntạicạnh âm. 4 1 5 6 09/04/2011 Lý thuyết đồ thị 4
5. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhất Nhậnxét: –Nếuvlàđỉnh trung gian trên đường đingắnnhấttừ s đếntthìđường đitừ s đếnvphảilàngắnnhấtvà đường đitừ v đếntcũng phảilàngắnnhất. s X v t –Do đó, để tối ưu, ngườitamở rộng bài toán tìm đường đingắnnhấttừ một đỉnh đếntấtcả các đỉnh còn lại của đồ thị. 09/04/2011 Lý thuyết đồ thị 5
6. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhất Ýtưởng chung củacácthuật toán tìm đường đingắnnhất – Dò tìm bằng cách thửđi qua các đỉnh trung gian –Nếupháthiện đường điquađỉnhtrunggianngắnhơn đường đihiệntạithìsẽ cậpnhật đường đimới, đồng thời chỉnh sửa các thông tin liên quan. –Sử dụng hai mảng để lưutrữ tạmthời: •Mảng d[v]: Lưutrữđộdài đường đingắnnhấthiệntại từ s đếnv. •Mảng T[v]: Lưutrữđỉnh nằmtrướcvtrênđường đi ngắnnhấthiệntại. 09/04/2011 Lý thuyết đồ thị 6
7. 5.1 Đồ thị có trọng số - Bài toán đường đingắnnhấ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
8. 5.2 Thuật toán Ford-Bellman //Khởitạo for v ∈ V { d[v]=c[s,v]; Truoc[v]=s; } //Bắt đầu d[s]=0; k1 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
9. 5.2 Thuật toán Ford-Bellman Cây kết quả: 1 2 3 k1 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
10. 5.2 Thuật toán Ford-Bellman k123456 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
11. 5.2 Thuật toán Ford-Bellman Cây kết quả 1 2 4 k123456 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
12. 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
13. 5.3 Thuật toán Dijkstra ƒNhận xét về Ford-Bellman: k123456 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ếtquả củabảng đã ổn định từ sớm – Trên một dòng, giá trị dnhỏ nhất không thay đổivề sau nếu trọng số các cạnh là không âm 09/04/2011 Lý thuyết đồ thị 13
14. 5.3 Thuật toán Dijkstra Chú ý: thuậttoánnàychỉ dùng cho đồ thị không có cạnh âm. Ýtưởng: – Do không có cạnh âm nên tạimỗibước, sẽ có một đỉnh mà thông tin về nó sẽ không thay đổivề sau –Tạimỗibước, ta không cầnphảikiểm tra qua tấtcả các đỉnh trung gian, mà chỉ thựchiệnnhư sau: •Chọnmột đỉnh u có giá trị d[u] nhỏ nhất •Chọnulàmđỉnh trung gian để xác định các bướckế tiếp 09/04/2011 Lý thuyết đồ thị 14
15. 5.3 Thuật toán Dijkstra //Khởitạo for v ∈ V { d[v]=c[s,v]; Truoc[v]=s; } d[s]=0; T=V\{s} ; //Tlàtập các đỉnh chưacốđịnh //Bướclặp while T!=∅ { k1 2 3 4 5 6 Tìm đỉnh u ∈ Tthoả 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
16. 5.3 Thuật toán Dijkstra Cây kết quả 1 2 4 k1 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
17. 5.4 Thuật toán Floyd – Đường đingắnnhấtgiữa tấtcả 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
18. 5.4 Thuật toán Floyd – Đường đingắnnhấtgiữa tấtcả các cặp đỉnh // Khởitạo 1 10 2 For (i=1; i d[i,k] + d[k,j]) { Ma trận d Ma trận p d[i,j] = d[i,k] + d[k,j]; p[i,j] = p[k,j]; } 09/04/2011 Lý thuyết đồ thị 18
19. 5.4 Thuật toán Floyd – Đường đingắnnhấtgiữa tấtcả các cặp đỉnh 10 ⎡⎤∞ 10 6 2 ⎡1111⎤ 1 2 ⎢⎥⎢ ⎥ 3 Khởi ⎢⎥10∞ 5 3 ⎢2222⎥ 2 6 5 tạo ⎢⎥65∞ 1 ⎢3333⎥ ⎢⎥⎢ ⎥ 231∞ 4444 1 ⎣⎦⎣ ⎦ 4 3 Ma trận d Ma trận p ⎡⎤∞ 10 6 2 ⎡1111⎤ ⎡∞ 10 6 2 ⎤ ⎡1111⎤ ⎢⎥⎢ ⎥ ⎢10∞ 5 3 ⎥ ⎢2222⎥ k=1 ⎢⎥10∞ 5 3 ⎢2222⎥ ⎢ ⎥ ⎢ ⎥ k=3 ⎢⎥65∞ 1 ⎢3333⎥ ⎢ 65∞ 1⎥ ⎢3333⎥ ⎢⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎦231∞ ⎣4444⎦ ⎣ 231∞⎦ ⎣4444⎦ ⎡⎤∞ 10 6 2 ⎡1111⎤ ⎡∞ 532⎤ ⎡1441⎤ ⎢⎥10∞ 5 3 ⎢2222⎥ ⎢ 543∞ ⎥ ⎢4242⎥ k=2 ⎢⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ k=4 ⎢⎥65∞ 1 ⎢3333⎥ ⎢ 34∞ 1⎥ ⎢4433⎥ ⎢⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎦231∞ ⎣4444⎦ ⎣ 231∞⎦ ⎣4444⎦ 09/04/2011 Lý thuyết đồ thị 19
20. 5.4 Thuật toán Floyd – Đường đingắnnhấtgiữa tấtcả các cặp đỉnh 1 10 2 ⎡∞ 532⎤ ⎡1441⎤ 3 ⎢ 543∞ ⎥ ⎢4242⎥ 2 6 5 ⎢ ⎥ ⎢ ⎥ ⎢ 34∞ 1⎥ ⎢4433⎥ 1 4 3 ⎢ ⎥ ⎢ ⎥ ⎣ 231∞⎦ ⎣4444⎦ –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