Bài giảng Lý thuyết đồ thị: Chương 5 - Tôn Quang Toại

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

10
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 5 Đường đi ngắn nhất trên đồ thị, cung cấp cho người đọc những kiến thức như: Các khái niệm mở đầu; Phát biểu bài toán; Thuật toán Dijkstra ;Thuật toán Ford – Bellman; Thuật toán Floyd. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 5 - Tôn Quang Toại

CHƯƠNG 5 ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
Nội dung Các khái niệm mở đầu Phát biểu bài toán Thuật toán Dijkstra Thuật toán Ford – Bellman Thuật toán Floyd
Các khái niệm mở đầu Đồ thị có trọng số: Đồ thị G=(V, E) có trọng số khi mỗi cạnh e=(u,v) của đồ thị được gán với một con số w(u,v) và được gọi là trọng số của cạnh e. Đường đi: Đường đi giữa 2 đỉnh s và t được cho bởi là dãy đỉnh trong đó:
Các khái niệm mở đầu Độ dài đường đi: Độ dài đường đi là tổng trọng số của tất cả các cạnh trên đường đi đó 𝑤 𝑝 𝑤 𝑥, 𝑥
Phát biểu bài toán Ví dụ: 18 p = (a, d, f, g) w(p) = 6 + 8 + 2 = 16 b 12 c 4 3 2 7 g a 6 d 8 2 3 9 4 f e 14
Các khái niệm mở đầu Biểu diễn đồ thị trọng số Cách 1: Ma trận trọng số 0/∞ 𝑛ế𝑢 𝑖, 𝑗 ∉ 𝐸 𝑣 𝑤 𝑖, 𝑗 𝑛ế𝑢 𝑖, 𝑗 ∈ 𝐸 int[,] v; int n;
Các khái niệm mở đầu Cách 2: Danh sách cạnh LinkedList e; Cách 3: Danh sách kề LinkedList[] v;
Phát biểu bài toán Phát biểu bài toán: Cho đồ thị G=(V, E) có trọng số và hai đỉnh s và t cho trước. Hãy tìm 1 đường đi từ s đến t sao cho độ dài đường đi là ngắn nhất
Phát biểu bài toán 18 Ví dụ: b 12 c p = (a, d, f, g) 4 3 2 w(p) = 6 + 8 + 2 = 16 7 g=t s=a 6 d 8 2 3 9 4 f e pshortest = (s, ,t) w(pshortest) = 14
Thuật toán Dijkstra Giả định của thuật toán Dijkstra Không có cạnh âm trong đồ thị s và t liên thông với nhau Ý tưởng thuật toán Dijkstra: Mỗi đỉnh của đồ thị, ta gán một giá trị dist[i]: là độ dài đường đi ngắn nhất từ s đến i. Nhiệm vụ: Giảm giá trị mảng dist[ ] từng bước.
Thuật toán Dijkstra Thuật toán Dijkstra: Input: G=(V, E) và 2 đỉnh s, t Output: 𝑑𝑖𝑠𝑡 Bước 1 (Khởi tạo) • 𝑑𝑖𝑠𝑡 𝑖 ∞, ∀𝑖 ∈ 𝑉 • 𝑑𝑖𝑠𝑡 𝑠 0 • Tập S=V (S là tập đỉnh chưa xét) Bước 2 (Lặp) • Tìm min: Chọn đỉnh 𝑎 ∈ 𝑆 sao cho 𝑑𝑖𝑠𝑡 𝑎 có giá trị nhỏ nhất • Cập Nhật: Với mọi đỉnh b kề đỉnh a – Nếu dist[b]>dist[a] + w(a,b) thì dist[b]=dist[a] + w(a,b) và pre[b]=a • S = S ‐ {a} (đỉnh a đã xét xong, bỏ khỏi tập S) Lặp cho đến khi t  S (đỉnh t được xét)
Thuật toán Dijkstra Giải thích bước cập nhật: Khi gán 𝑑𝑖𝑠𝑡 𝑏 𝑑𝑖𝑠𝑡 𝑎 𝑤 𝑎, 𝑏 tức là ta đã phát hiện ra 1 đường đi mới đến b có độ dài ngắn hơn 𝑑𝑖𝑠𝑡 𝑏 𝑏 𝑑𝑖𝑠𝑡 𝑏 𝑑𝑖𝑠𝑡 𝑎 𝑤 𝑎, 𝑏 𝑤 𝑎, 𝑏 Đường đi cũ Đường đi mới 𝑠 𝒂 𝑑𝑖𝑠𝑡 𝑎 Và đường đi đó trước khi tới b phải qua a vì vậy để tìm liệt kê các đỉnh đường đi chúng ta dùng 1 mảng pre[]. Trong đó pre[b]=a cho biết đỉnh ngay trước đỉnh b là đỉnh a.
Ví dụ Ví dụ 1: Dùng thuật toán Dijkstra Tìm đường đi ngắn nhất từ a đến g 18 b 12 c 4 3 2 7 g=t s=a 6 d 8 2 3 9 4 f e 14
Ví dụ Lưu ý: Thuật toán Dijkstra có thể áp dùng tìm đường đi ngắn nhất từ một đỉnh đến tất các các đỉnh còn lại (chúng ta chỉ cần sửa lại điều kiện kết thúc vòng lặp là S=Ø)
Ví dụ Ví dụ 2: Tìm đường đi ngắn nhất từ đỉnh c đến các đỉnh còn lại theo thuật toán Dijkstra b 5 d 5 f 4 3 3 a 2 2 1 h 1 3 1 c 6 3 g e
Cài đặt Cấu trúc dữ liệu: dist[i]: Lưu độ dài đường đi ngắn nhất từ s đến i pre[i]: Lưu đỉnh trước của đỉnh i label[i]: true: 𝒊 ∉ 𝑺 false: 𝒊 ∈ 𝑺 path[]: lưu các đỉnh của đường đi
Cài đặt Input LinkedList[] v; int s; Output int[] dist; bool[] label; int[] pre; LinkedList path;
Cài đặt void Dijkstra(int s) { // B1: Khởi tạo for (int i=0; i
Cài đặt void TruyVet(int s, int t) { path = new LinkedList(); for (i=t; i!=-1; i=pre[i]) path.AddFirst(i); }
Thuật toán Bellman – Ford Thuật toán Dijkstra không thể thực hiện khi đồ thị có cạnh âm (đồ thị vô hướng) hay đồ thị có chu trình âm có thể đến được (đồ thị có hướng) Thuật toán Bellman – Ford xác định các chu trình âm hay trả về cây đường đi ngắn nhất