Bài giảng Toán - Chương 8: Bài Toán Đường Đi Ngắn Nhất

CHƯƠNG 8	BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT1NỘI DUNGBài toán đường đi ngắn nhấtĐường đi có trọng số bé nhấtThuật toán DijsktraĐường đi trên đồ thị phi chu trìnhĐường đi ngắn nhất giữa các cặp đỉnhTâm của đồ thị28.1. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤTBài toán: Cho đồ thị G = (V, E) và hai đỉnh a, b. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh b trong đồ thị G. Ý nghĩa thực tế: 	Bài toán giúp chúng ta chọn các hành trình tiết kiệm nhất (quãng đường, thời gian, chi phí ...) trong giao thông, lập lịch thi công công trình một cách tối ưu, xử lý trong truyền tin ...38.1. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT (tiếp) Thuật toán duyệt đồ thị theo chiều rộng đã cho ta lời giải của bài toán này. Song ta có thêm thuật toán sau đây.4TÌM ĐƯỜNG ĐI NGẮN NHẤT 1) Lần lượt gán nhãn cho các đỉnh của đồ thị, mỗi đỉnh không quá một lần, như sau:	- Đỉnh a được gán nhãn là số 0.	- Những đỉnh kề với đỉnh a được gán số 1.	- Những đỉnh kề với đỉnh đã được gán nhãn số 1, được gán số 2.	- Tương tự, những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số i+1.	5TÌM ĐƯỜNG ĐI NGẮN NHẤT (tiếp)	2) Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn được nữa.Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k, ngược lại thì trả lời là không có.6TÌM ĐƯỜNG ĐI NGẮN NHẤT (tiếp)Khôi phục đường đi	Nếu ở bước 2 chỉ ra b được gán nhãn k nào đó thì ta đi ngược lại theo quy tắc sau đây: Nếu đỉnh y được gán nhãn j với j  1 thì sẽ có đỉnh x được gãn nhãn j-1 sao cho có cạnh đi từ x tới y. 	Đi ngược lại cho đến khi gặp đỉnh a, ta nhận được đường đi ngắn nhất cần tìm. 7BÀI TOÁN SÓI, DÊ VÀ BẮP CẢI	Một con sói, một con dê và một cái bắp cải đang ở bờ sông. Người lái đò phải đưa chúng sang sông. Nhưng thuyền quá bé nên mỗi chuyến chỉ chở được một “hành khách” thôi. Vì những lý do mà ai cũng biết, không thể bỏ mặc sói với dê hoặc dê với bắp cải mà không có người trông. 	Vậy người lái đò phải xử trí thế nào mà vẫn đưa được sói, dê và bắp cải sang bên kia sông. 8BÀI TOÁN SÓI, DÊ VÀ BẮP CẢI (tiếp)	Xây dựng đồ thị vô hướng với các đỉnh thể hiện các hành khách còn lại bên phía xuất phát tại mỗi thời điểm khác nhau. Cạnh nối hai đỉnh thể hiện một chuyến đò qua sông. 	Hình 8.1. Hành trình qua sông của sói, dê và bắp cảiSBaLSDBDSBØBLSDLDBLSBLD98.2. ĐỒ THỊ CÓ TRỌNG SỐ Định nghĩa 8.1: Đồ thị G được gọi là đồ thị có trọng số nếu trên mỗi cạnh (i, j) của đồ thị được gán một số nguyên không âm c(i,j). 	Nhãn c(i,j) trên cạnh (i, j) của đồ thị thường biểu diễn “chi phí” thực tế để đi qua cạnh này. 	Ký hiệu đồ thị có trọng số là (G, c). 	108.3. ĐƯỜNG ĐI CÓ TRỌNG SỐ BÉ NHẤT	- Độ dài của đường đi trong đồ thị có trọng số bằng tổng các trọng số của các cạnh trên đường đi đó.	- Độ dài đường đi có trọng số bé nhất đi từ đỉnh a đến đỉnh b được gọi là khoảng cách từ đỉnh a đến đỉnh b. 	- Nếu không có đường đi từ a đến b thì đặt khoảng cách bằng . 118.3. ĐƯỜNG ĐI CÓ TRỌNG SỐ BÉ NHẤT (tiếp)Bài toán 	Cho đồ thị có trọng số (G, c) và hai đỉnh a, b thuộc G. Hãy tìm đường đi có trọng số bé nhất (nếu có) đi từ đỉnh a đến đỉnh b.128.4. THUẬT TOÁN DIJKSTRA Năm 1959 E. W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. 	Thuật toán thực hiện việc gán và giảm giá trị của nhãn l(i) tại mỗi đỉnh i của đồ thị G như sau:138.4. THUẬT TOÁN DIJKSTRA (tiếp) Thuật toán 8.2 	1. Với đỉnh xuất phát a, gán nhãn l(a) := 0.	2. Nếu có cạnh (i, j) mà đỉnh i đã được gán nhãn và đỉnh j chưa được gán nhãn hoặc đỉnh j đã được gán nhãn nhưng l(i) + c(i,j) L[i] + C[i, j] then12	begin 13	 L[j] := L[i] + C[i, j] ;14	 Truoc[j] := i ;15	end 18	end 19 end ;	Biến mảng Truoc dùng để khôi phục đường đi.228.5. ĐƯỜNG ĐI TRÊN ĐỒ THỊ PHI CHU TRÌNHSử dụng Thuật toán 4.1 để đánh số các đỉnh trên đồ thị định hướng phi chu trình, ta xây dựng được thuật toán ngắn gọn hơn để tìm khoảng cách từ đỉnh nguồn tới tất cả các đỉnh trong một đồ thị phi chu trình. 238.5. ĐƯỜNG ĐI TRÊN ĐỒ THỊ PHI CHU TRÌNH (tiếp)Thuật toán 8.3:	Dữ liệu: Biểu diễn mảng DK_V các danh sách kề của đồ thị định hướng phi chu trình G = (V, E) với tập đỉnh V = {v1, v2, ..., vn} đã được đánh số mà danh sách DK_V[vi] chứa các đỉnh nhận vi là đỉnh kề và ma trận trọng số C của đồ thị G.	Kết quả: Mảng D các số nguyên với D[vi] chứa khoảng cách d(v1,vi) , i = 2, 3, ..., n. 248.5. ĐƯỜNG ĐI TRÊN ĐỒ THỊ PHI CHU TRÌNH (tiếp)1 Begin2 D[v1] := 0 ;3 for j := 2 to n do D[vj] :=  ;4 for j := 2 to n do for vi  DK_V[vj] do D[vj] := min ( D[vj] , D[vj] + C[vi,vj] ) 7 End.258.5. ĐƯỜNG ĐI TRÊN ĐỒ THỊ PHI CHU TRÌNH (tiếp)Tính đúng đắn của thuật toán suy từ chi tiết sau đây: 	- Tất cả các đỉnh trung gian trên đường đi ngắn nhất từ v1 tới vj có chỉ số nhỏ hơn j. 	- Mỗi cạnh (vi,vj) được xét trong dòng lệnh 5 đúng một lần. Độ phức tạp của thuật toán là O(m). 268.5. ĐƯỜNG ĐI TRÊN ĐỒ THỊ PHI CHU TRÌNH (tiếp)Ta cũng có thể áp dụng thuật toán trên để tìm đường đi dài nhất từ đỉnh nguồn tới các đỉnh khác của đồ thị, hoặc tìm đường đi dài nhất trên đồ thị định hướng phi chu trình có trọng số. 27VÍ DỤ 8.3Tìm đường đi dài nhất trên đồ thị định hướng phi chu trình có trọng số dưới đây:111122233445555667789Hình 8.3. Đường đi dài nhất trên đồ thị phi chu trình có trọng số288.6. ĐƯỜNG ĐI NGẮN NHẤT GIỮA CÁC CẶP ĐỈNHBài toán: Cho một đồ thị có trọng số (G, c).Hãy tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh.Bài toán này thường gặp trong việc xây dựng bảng khoảng cách giữa các thành phố, bảng giá cước vận chuyển giữa các nhà ga ... 298.6. ĐƯỜNG ĐI NGẮN NHẤT GIỮA CÁC CẶP ĐỈNH (tiếp)Bài toán này có thể giải quyết bằng cách sử dụng thuật toán Dijkstra với mỗi đỉnh của đồ thị lần lượt là các đỉnh xuất phát. Ta có thể giải quyết bài toán trực tiếp bằng thuật toán Floyd.308.6. ĐƯỜNG ĐI NGẮN NHẤT GIỮA CÁC CẶP ĐỈNH (tiếp)Sử dụng ma trận Dn x n để tính độ dài đường đi ngắn nhất giữa tất cả các cặp đỉnh. 	1) Bắt đầu gán D := C - ma trận trọng số.	2) Thực hiện n lần lặp trên D. Sau bước lặp thứ k, D[i,j] chứa độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j mà chỉ đi qua các đỉnh có chỉ số không vượt quá k:	D(k)[i,j] := min ( D(k-1)[i,j] , D(k-1)[i,k] + D(k-1)[k,j] ) ,	 với k = 1, 2, ... , n.31VÍ DỤ 8.4Xét bản đồ giao thông sau đây: 	Kết quả tính toán:	abc8342Hình 8.4. Bản đồ giao thôngD1D2D4408020347080203D347080203547060203532THUẬT TOÁN FLOYDThuật toán 8.5 (Floyd)Dữ liệu: Ma trận trọng số C của đồ thị.Kết quả: Ma trận D cho biết khoảng cách của tất cả các cặp đỉnh.33THUẬT TOÁN FLOYD (tiếp)1 BEGIN2 for i := 1 to n do 3 for j := 1 to n do 4	 begin D[i,j] := C[i,j] ; TRUOC[i,j] := 0 end ;5 for k := 1 to n do 6	 for i := 1 to n do 7	 for j := 1 to n do 8	 if D[i,k] + D[k,j] .THUẬT TOÁN FLOYD (tiếp)010300002378.7. TÂM CỦA ĐỒ THỊ	Giả sử G = (V, E) là một đồ thị có trọng số không âm trên các cạnh.	Ký hiệu: d(x,y) là khoảng cách giữa đỉnh x và đỉnh y trong đồ thị G.	Đại lượng d(a) = max { d(x,a)x  V } được gọi là độ lệch của đỉnh a trong đồ thị G.388.7. TÂM CỦA ĐỒ THỊ (tiếp)Định nghĩa 8.2	- Bán kính R của đồ thị G là độ lệch bé nhất trên các đỉnh: 	R = min { d(a)  a  V}.	- Tâm của đồ thị G là đỉnh a có độ lệch bé nhất: 	  x  V, d(a)  d(x). 398.7. TÂM CỦA ĐỒ THỊ (tiếp)- Đường kính của đồ thị G là khoảng cách dài nhất giữa các cặp đỉnh trong đồ thị: 	 d = max { d(x,y)  x, y  V }.	40	VÍ DỤ 8.5Cho đồ thị G như sau:	Vậy tâm của đồ thị là đỉnh d.abced1124523Hình 8.5. Đồ thị có trọng sốĐộ lệch685 – bán kính7Đỉnhabcde418.7. TÂM CỦA ĐỒ THỊ (tiếp)Ý nghĩa của tâm đồ thị: Dùng để xác định:	- Thủ đô của một nước 	- Nút giao thông quan trọng trong một thành phố	- Vị trí đặt máy chủ trong một mạng máy tính ...42THUẬT TOÁN TÌM TÂM CỦA ĐỒ THỊThuật toán 8.5:	1. Dùng thuật toán Floyd để tính ma trận D các khoảng cách của các cặp đỉnh.	2. Tìm giá trị lớn nhất trên mỗi cột, cho ta độ lệch của đỉnh tương ứng.	3. Tìm đỉnh với độ lệch bé nhất, đó chính là tâm của đồ thị.43	VÍ DỤ 8.6Ma trận khoảng cách D của ví dụ trên là:	 a b c d e 	Tâm: d	Bán kính: 5	Đường kính: 	 	  6 8 5 7Nếu vẽ một vòng tròn có tâm và bán kính như định nghĩathì tất cả các đỉnh của đồ thị sẽ nằm trong vòng tròn này. 76470542053203810316044