Luận văn tốt nghiệp - Đường đi ngắn nhất trong đồ thị

Trong các ứng dụng thực tế bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có ý nghĩa rất lớn. Bài toán tìm đường đi ngắn nhất được ứng dụng trong thực tế như để chọn một hành trình tiết kiệm nhất (về thời gian hoặc chi phí) trên một mạng giao thông đường thuỷ, đường bộ hoặc đường không. Bài toán lập lịch thi công các công đoạn trong một công trình thi công lớn. Bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin... Dùng...
Nội dung trích xuất từ tài liệu:
Luận văn tốt nghiệp - Đường đi ngắn nhất trong đồ thịLuận văn tốt nghiệp Chương 4 ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊGiới thiệu: Trong các ứng dụng thực tế bài toán tìm đường đi ngắn nhất giữa hai đỉnh củamột đồ thị liên thông có ý nghĩa rất lớn. Bài toán tìm đường đi ngắn nhất đượcứng dụng trong thực tế như để chọn một hành trình tiết kiệm nhất (về thời gianhoặc chi phí) trên một mạng giao thông đường thuỷ, đường bộ hoặc đườngkhông. Bài toán lập lịch thi công các công đoạn trong một công trình thi cônglớn. Bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thôngtin... Dùng thuật giải đường đi ngắn nhất trong đồ thị giải quyết bài toán sửa góitin sai trong việc truyền tin... dưới đây ta xét một số thuật toán để tìm đường đingắn nhất trong đồ thị có trọng số và đồ thị không có trọng số.I. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ KHÔNG CÓ TRỌNG SỐ 1. Định nghĩa: Đồ thị không có trọng số là đồ thị hữu hạn trên các cạnhkhông có trọng số. Bài toán tìm đường đi ngắn nhất giữa hai đỉnh a,b trong đồthị không có trọng số G = là tìm đường đi giữa hai đỉnh a, b sao cho cósố các cạnh (cung) là ít nhất.2. Thuật toán:Bước 1: Tại đỉnh a ta ghi số 0Các đỉnh có cạnh đi từ đỉnh a đến ta ghi số 1.Giả sử ta đã ghi tới i, tức là ta đã đánh số được các tập đỉnh là A(0) = {a}, A(1),A(2), ... , A(i) trong đó A(i) là tập tất cả các đỉnh được ghi bởi số i. Ta xác địnhtập đỉnh được đánh số bởi số i + 1 là A(i+1) = {x / x X, x A(k) với k = 0,...,i và tồn tại y A(i) sao cho từ y có cạnh (cung) tới x}. Do tính hữu hạn củađồ thị, sau một số hữu hạn các bước, thuật toán dừng lại và cho kết quả là tậpcác đỉnh có chứa b được đánh số bởi m là A(m).Bước 2: Do bước 1 thì đỉnh b được đánh số bởi m, điều này chứng tỏ đường đitừ a đến b có m cạnh (cung) và là đường ngắn nhất đi từ a đến b. Để tìm tất cảcác đường có độ dài m ngắn nhất đi từ a đến b, ta xuất phát từ b đi ngược về atheo đúng nguyên tắc sau đây: 42Luận văn tốt nghiệp - Tìm tất cả các đỉnh có cạnh (cung) tới b được ghi số m - 1, giả sử đó là xik (k= 1, 2,...). - Với mỗi đỉnh xik tìm tất cả các đỉnh có cạnh (cung) với xik (k = 1, 2, ...) đượcghi số m -2.Bằng cách lùi dần trở lại, đến một lúc nào đó gặp đỉnh ghi số 0, đó chính là đỉnha. Tất cả các đường xác định theo các bước trên là đường đi từ a đến b có độ dàingắn nhất là m cần tìm. 1 2 3 x1 x2 x3 x4 0 1 2 3 a x6 x5 b x7 x8 x9 x10 1 2 3 Hình 1.1 Ví dụ đồ thị như hình 1.1 xây dựng đường đi ngắn nhất theo thuật toán trên:Bước 1: Đỉnh a được đánh số 0 và có A(0) = {a} A(1) = {x1, x6, x7} A(2) = {x2, x5, x8} A(3) = {x3, b, x9}Bước 2: Từ bước 1 ta có b A(3) nên từ a đến b là đường đi ngắn nhất có 3cung. Tiếp theo ta xác định tất cả các đường đi ngắn nhất có độ dài 3: Đỉnh có cung về b được đánh số 2 là x5 Đỉnh có cung tới x5 được đánh số 1 là x6 Đỉnh có cung về x6 được đánh số 0 là aVậy đường cần tìm là a - x6 - x5 - b.II. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ CÓ TRỌNG SỐ1. Các khái niệm Cho đồ thị hữu hạn G = với mỗi cạnh u U ta đặt tương ứng với sốdương l(u) gọi là trọng số của u.Đồ thị có cạnh như trên được gọi là đồ thị có trọng số.Gọi là một đường đi nào đó trong G = Giả sử = xi1ui1xi2ui2 ... xin - 1uin-1xin, xij X , uij U (j = 1, 2, ...,n). n −1Khi đó ký hiệu l (α ) = ∑ l (u j ij ) gọi là trọng số của đường 43Luận văn tốt nghiệpTa ký hiệu D(a,b) là tập tất cả các đường đi nối đỉnh a với đỉnh b trong đồ thị G.Đường đi giữa a và b là ngắn nhất nếu thoả mãn l( ) = min {l( ) /D(a,b)}Bài toán: Cho đơn đồ thị G = liên thông có trọng số, và a, b X. Tìmcác đường đi ngắn nhất giữa 2 đỉnh a, b.2. Thuật toán tìm đường đi ngắn nhất cho đồ thị có trọng số2.1 Cơ sở thuật toán tìm đường đi ngắn nhất Cho G = tìm đường đi ngắn nhất từ đỉnh a tới đỉnh bVới x X nếu độ dài đường đi từ đỉnh xuất phát tới đỉnh x có trọng số là l( )thì (x) = l( ) gọi là trọng số của đỉnh x. Cơ sở của tất cả các thuật toán tìmđường đi ngắn nhất là xác định được các trọng số nhỏ nhất cho tất cả các đỉnh từđó tìm đường đi ngắn nhất.Bước 1: Đánh trọng số các đỉnh, trọng số của đỉnh xuất phát là (a) = 0.Tại các đỉnh còn lại ta ghi một số dương nào đó sao cho nó đủ lớn hơn trọng số ...