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 đó. | 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 ỉjJ 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 ijj i j ỉ 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 . Chương II GIẢI THUẬT_LƯU ĐỒ THUẬT TOÁN DIJKSTRA 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ừ s tớ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ông kề s. SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 34 Giải thuật tìm đường đi ngắn nhất giữa một cặp đỉnh. Định nghĩa . Xét đồ thị có trọng số cạnh G VE w với hàm trọng số w E R là ánh xạ từ tập các cạnh E đến tập số thực R. Định nghĩa . Đường đi p từ đỉnh u đến đỉnh v là dãy các cạnh nối tiế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ểu diễn như sau p u v0 vi. vk v Định nghĩa . Độ dài của đường đi p v0 V . vk ký hiệu Cũ p là tổng các trọng số của các cạnh trên đường đi k ữ p E w vi-1 vi i 1 Định nghĩa . Gọi p 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 Gfc u v Định nghĩa . Đường đi ngắn nhấtpmin u v từ đỉnh u đến đỉnh v là đường đi có độ dài d u v . Giải thuật Dijkstra. .
