Bài giảng Lý thuyết đồ thị - Chương 7: Bài toán tìm đường đi ngắn nhất

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 7: Bài toán tìm đường đi ngắn nhất

1. Môn học: Lý thuyết đồ thị Chương 7: Bài toán tìm đường đi ngắn nhất Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
2. Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 – Bài toán tìm đường đi ngắn nhất 2 Lý thuyết đồ thị
3. I. Giới thiệu ™Xét đồ thị có hướng, có trọng số G=(V, E) ⎧∞ , if (u,v)∉ E TrongSo(u,v) = ⎨ ⎩a(u,v), if (u,v)∈ E Với a(u, v) ∈ R ™Nếu dãy v0,v1, ,vp là 1 đường đi trên G thì độ dài của nó được định nghĩa: p DoDai (v0 , v1 , , v p ) = ∑ a(vi−1 , vi ) i=1 Chương 7 – Bài toán tìm đường đi ngắn nhất 3
4. I. Giới thiệu ™Bài toán đường đi ngắn nhất ƒ Giả sử có nhiều đường đi từ v0 đến vp: Đường đi ngắn nhất là đường đi có tổng trọng số các cung nhỏ nhất. ƒ Đường đi từ một đỉnh • Ford-Bellman • Dijkstra ƒ Đường đi từ một đỉnh • Floyd Chương 7 – Bài toán tìm đường đi ngắn nhất 4
5. Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 – Bài toán tìm đường đi ngắn nhất 5 Lý thuyết đồ thị
6. II. Thuật toán Ford-Bellman ™ Thuật toán Ford-Bellman dùng để tìm đường đi ngắn nhất từ một đỉnh s đến tất cả các đỉnh còn lại của đồ thị. ™ Được sử dụng cho đồ thị không có chu trình âm. Cho đồ thị có hướng, có trọng số G=(V, E). Trọng số của các cạnh của G được tính như sau: TrongSo(u, v) = ∞ nếu cung (u, v) ∉ E. TrongSo(u, v) = a(u, v) nếu cung (u, v) ∈ E. Thuật toán tìm đường đi ngắn nhất d(v) từ đỉnh s đỉnh v, mọi v ∈ V: + Xét u V. Nếu d(u) + TrongSo(u, v) < d(v) thì ta thay d(v) = d(u) + TrongSo(u, v). + Quá trình này sẽ được lặp lại cho đến khi không thể có giá trị d(v) tốt hơn. Chương 7 – Bài toán tìm đường đi ngắn nhất 6
7. II. Thuật toán Ford-Bellman ™Cài đặt thuật toán ƒ Đầu vào: • Đồ thị có hướng G=(V,E) với n đỉnh. • s ∈ V là đỉnh xuất phát. • a[u,v], u,v ∈ V là ma trận trọng số ƒ Đầu ra : • Khoảng cách từ s đến tất cả các đỉnh còn lại d[v], v ∈ V . • Truoc[v], v ∈ V là đỉnh đi trước v trong đường đi ngắn nhất từ s đến v Chương 7 – Bài toán tìm đường đi ngắn nhất 7
8. II. Thuật toán Ford-Bellman void Ford_Bellman() { for (v ∈ V) /* Khởi tạo d và Truoc */ { d[v] = a[s,v]; Truoc[v] = s; } d[s] = 0; for (k = 1; k d[u] + a[u,v] ) { d[v] = d[u] + a[u,v] ; Truoc[v] = u; } } /* Độ phức tạp của thuật toán là O(n3) */ Chương 7 – Bài toán tìm đường đi ngắn nhất 8
9. II. Thuật toán Ford-Bellman ™ Ví dụ 1 2 3 4 5 1 ∞ 1 ∞∞3 2 ∞∞ 3 3 8 3 ∞∞ ∞ 1 -5 4 ∞∞ 2 ∞∞ 5 ∞∞ ∞ 4 ∞ k d[5], Truoc[5] d[4], Truoc[4] d[3], Truoc[3] d[2], Truoc[2] 13, 1 ∞, 1 ∞, 1 1, 1 2 3, 1 4, 2 4, 2 1, 1 3 -1, 3 4, 2 4, 2 1, 1 4 -1, 3 3, 5 4, 2 1, 1 5 -1, 3 3, 5 4, 2 1, 1 Chương 7 – Bài toán tìm đường đi ngắn nhất 9
10. Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 – Bài toán tìm đường đi ngắn nhất 10 Lý thuyết đồ thị
11. III. Thuật toán Dijkstra ™ Thuật toán Dijkstra dùng để tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại trong đồ thị. ™ Được sử dụng cho đồ thị không có cung trọng số âm. ™ Thuật toán ƒ Đầu vào • Đồ thị có hướng G=(V,E) với n đỉnh. • s ∈ V là đỉnh xuất phát. • a[u,v], u,v ∈ V là ma trận trọng số ƒ Đầu ra • Khoảng cách từ s đến tất cả các đỉnh còn lại d[v], v ∈ V . • Truoc[v], v ∈ V là đỉnh đi trước v trong đường đi ngắn nhất từ s đến v. Chương 7 – Bài toán tìm đường đi ngắn nhất 11
12. III. Thuật toán Dijkstra void Dijkstra;{ for (v ∈ V) /* Khởi tạo d và Truoc */ { d[v] = a[s,v]; Truoc[v] = s; } d[s] = 0; T = V \ {s}; while (T != ∅ ) { Tìm u ∈ T sao cho d(u) = min { d(z): z ∈ T } T = T \ {u}; /* Cố định nhãn của u */ for (v ∈ T) do if (d[v] > d[u] + a[u,v] ) then { d[v] = d[u] + a[u,v] ; Truoc[v] = u; } } } /* Độ phức tạp của thuật toán là O(n2) */ Chương 7 – Bài toán tìm đường đi ngắn nhất 12
13. III. Thuật toán Dijkstra ™ Ví dụ 1 2 3 4 5 1 ∞ 1 ∞∞7 2 ∞∞ 1 4 8 3 ∞∞ ∞ 2 4 4 ∞∞ 1 ∞∞ 5 ∞∞ ∞ 4 ∞ T Đỉnh 2 Đỉnh 3 Đỉnh 4 Đỉnh 5 2, 3, 4, 5 1, 1 ∞,1 ∞, 1 7, 1 3, 4, 5 2, 2 5, 2 7, 1 4, 5 4, 3 6, 3 E6, 3 ∅ 1, 1 2, 2 4, 3 6, 3 Chương 7 – Bài toán tìm đường đi ngắn nhất 13
14. Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 – Bài toán tìm đường đi ngắn nhất 14 Lý thuyết đồ thị
15. IV. Thuật toán Floyd ™Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị. ™Thuật toán ƒ Với mọi đỉnh k của đồ thị xét theo thứ tự từ 1 đến n, xét mọi cặp đỉnh u, v. Ta tìm đường đi ngắn nhất từ u đến v theo công thức: a(u, v) = min (a(u, v), a(u, k) + a(k, v)) Chương 7 – Bài toán tìm đường đi ngắn nhất 15
16. IV. Thuật toán Floyd ™Cài đặt ƒ Đầu vào • Đồ thị cho bởi ma trận trọng số: a[i, j], i, j = 1, 2, , n. ƒ Đầu ra: Hai ma trận • Ma trận đường đi ngắn nhất giữa các cặp đỉnh: d[i, j], i, j = 1 n. d[i, j] là độ dài đường đi ngắn nhất từ i đến j • Ma trận ghi nhận đường đi. p[i, j], i, j = 1 n. p[i, j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất từ i đến j. Chương 7 – Bài toán tìm đường đi ngắn nhất 16
17. IV. Thuật toán Floyd void Floyd;{ for (i = 1; i d[i,k] + d[k,j]) { d[i,j] = d[i,k] + d[k,j]; p[i,j] = p[k,j]; } } Chương 7 – Bài toán tìm đường đi ngắn nhất 17
18. IV. Thuật toán Floyd ™Ví dụ Chương 7 – Bài toán tìm đường đi ngắn nhất 18
19. IV. Thuật toán Floyd Vậy đường đi ngắn nhầt từ đỉnh 1 đến đỉnh 3 là: 1 Æ 2 Æ 3. Với trọng số = 0. Chương 7 – Bài toán tìm đường đi ngắn nhất 19