Đồ án cơ sở -5

không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát , sử dụng thuật toán Ford-Bellman n lần không phải là cách làm tốt nhất . Ở đây ta sẽ mô tả thuật toán với độ phức tạp tính toán O(n3) : thuật toán Floyd, tt được mô tả như sau Procedure Floyd; (* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh Đầu vào : Đồ thị cho bởi ma trận trọng số a[i,j], i,j=1,2,...,n Đầu ra : Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i,j] i,j =1,2,...,n trong đó...
Nội dung trích xuất từ tài liệu:
Đồ án cơ sở -5không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát , sử dụngthuật toán Ford-Bellman n lần không phải là cách làm tốt nhất . Ở đây ta sẽ mô tảthuật toán với độ phức tạp tính toán O(n3) : thuật toán Floyd, tt được mô tả nhưsauProcedure Floyd;(* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh Đầu vào : Đồ thị cho bởi ma trận trọng số a[i,j], i,j=1,2,...,n Đầu ra : Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i,j] i,j =1,2,...,n trong đó d[i,j] cho độ dài đường di ngắn nhất từ i đến j. Ma trận ghi nhận đường đi p[i,j], i, j=1,2,...,n. trong đó p[i,j] ghi nhận đỉnh đi trước j trong đường đi ngắn nhất từ i đến j.*)Begin (* Khởi tạo *) For i:=1 to n do For j:=1 to n do Begin d[i,j]:=a[i,j];SVTH : Nguyễn Công Hiếu_SBD 0041 - Trang 33- p[i,j]:=i; end; (* Bước lặp *)For k:=1 to n do For i:=1 to n do For j:=1 to n do If d[i,j] > d[i,k] + d[k,j] then Begin d[i,j]:= d[i,k] + d[k,j ]; p [i,j ]:= p [k,j ]; end;end;Rõ ràng độ phức tạp của thuật toán là O(n3). GIẢI THUẬT_LƯU ĐỒ THUẬT TOÁN DIJKSTRAChương II :II.1 Phân tích. Dùng ma trận kề để biểu diễn đồ thị C= (cij), cij = trọng số của cung (i,j), cij =+∞ nếu không có cung (i,j). Một mảng d[] để ghi các độ dài đường đi ngắn nhất từ stới đỉnh i đang có . Xuất phát d[s] =0 và d[i] =c si nếu i kề s, d[j] =+ ∞ nếu j khôngkề s.SVTH : Nguyễn Công Hiếu_SBD 0041 - Trang 34-II.2 Giải thuật tìm đường đi ngắn nhất giữa một cặp đỉnh. Định nghĩa 1.0. Xét đồ thị có trọng số cạnh G = (V,E,w), với hàm trọng số w:E Rlà ánh xạ từ tập các cạnh E đến tập số thực R. Định nghĩa 1.1. Đường đi p từ đỉnh u đến đỉnh v là dãy các cạnh nốitiếp nhau bắt đầu từ đỉnh u kết thúc tại đỉnh v. Đường đi p từ u đến v được biểudiễn như sau: p=(u=v0,v1…,vk=v) Định nghĩa 1.2. Độ dài của đường đi p = ( v0,v1,...,vk ), ký hiệu  (p),là tổng các trọng số của các cạnh trên đường đi: k  w(v , vi )  (p) = i 1 i 1 Định nghĩa 1.3. Gọi (u,v) là tập tất cả đường đi từ u đến v. Độ dàiđường đi ngắn nhất từ đỉnh u đến đỉnh v được xác định bởi:d(u,v) = min { ( p ) | p (u , v )} Định nghĩa 1.4. Đường đi ngắn nhất pmin(u,v) từ đỉnh u đến đỉnh v làđường đi có độ dài d(u,v).II.3 Giải thuật Dijkstra. II.3.1 Nội dungSVTH : Nguyễn Công Hiếu_SBD 0041 - Trang 35-Có rất nhiều giải thuật đã được phát triển để giải bài toán tìm đường đi ngắn nhấtgiữa một cặp đỉnh, trong khuôn khổ bài viết này em chỉ xin giới thiệu giải thuậtDijkstra. Giải thuật Dijkstra là một giải thuật để giải bài toán đường đi ngắn nhấtnguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm.Nó xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b. Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: kv, dv và pv. kv: mang giá trị boolean xác định trạng thái được chọn của đỉnh v. Ban đầu ta khởi tạo tất cả các đỉnh v chưa được chọn, nghĩa là: kv = false,  v  V. dv: là chiều dài đường đi mà ta tìm thấy cho đến thời điểm đang xét từ a đến v. Khởi tạo, dv = , v  V {a}, da = 0. pv: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a đến b. Đường đi ngắn nhất từ a đến b có dạng {a,...,pv,v,...,b}. Khởi tạo, pv = null, v V. Sau đây là các bước của giải thuật Dijkstra: Khởi tạo: Đặt kv:= false v  V; dv:= ,v  V {a}, da:=0. B1. Chọn v  V sao cho kv = false và dv = min {dt / t V, kt = false} B2. Nếu dv =  thì kết thúc, không tồn tại đường đi từ a đến b. Đánh dấu đỉnh v, kv:= true. B3.SVTH : Nguyễn Công Hiếu_SBD 0041 - Trang 36- Nếu v = b thì kết thúc và db là độ dài đường đi ngắn nhất từ a đến b. B4. Ngược lại nếu v  b sang B5. Với mỗi đỉnh u kề với v mà ku = false, kiểm tra B5. Nếu du > dv + w(v,u) thì du:= dv + w(v,u) Ghi nhớ đỉnh v: pu:= v.Quay lại B2. II.3.2 Độ phức tạp của giải thuật Dijkstra.*** Trường hợp sử dụng ma trận kề. Gọi f(n) là số lần giải thuật Dijks ...