Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu part 10', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Cấu trúc dữ liệu Chương V Đồ thị D u-1 D w-1 C w-1 u-1 P u-1 w Ví dụ áp dụng giải thuật Dijkstra cho đồ thị hình Kết quả khi áp dụng giải thuật Lần lặp S W D 2 D 3 D 4 D 5 Khởi đầu 1 - 10 TO 30 100 1 1 2 2 10 60 30 100 2 1 2 4 4 10 40 30 90 3 1 2 3 4 3 10 40 30 50 4 1 2 3 4 5 5 10 40 30 50 Mảng P có giá trị như sau P 1 2 3 4 5 1 4 1 3 Từ kết quả trên ta có thể suy ra rằng đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là 1 4 3 có độ dài là 40. đường đi ngắn nhất từ 1 đến 5 là 1 4 3 5 có độ dài 50. 2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh Giả sử đồ thị G có n đỉnh được đánh số từ 1 đến n. Khoảng cách hay giá giữa các cặp đỉnh được cho trong mảng C i j . Nếu hai đỉnh i j không được nối thì C i j . Giải thuật Floyd xác định đường đi ngắn nhất giữa hai cặp đỉnh bất kỳ bằng cách lặp k lần ở lần lặp thứ k sẽ 145 Cấu trúc dữ liệu Chương V Đồ thị xác định khoảng cách ngắn nhất giữa hai đỉnh i j theo công thức Ak i j min Ak-1 i j Ak-1 i k Ak-1 k j . Ta cũng dùng mảng P để lưu các đỉnh trên đường đi. float A n n C n n int P n n void Floyd int i j k for i 1 i n i for j 1 j n j A i-1 j-1 C i-1 j-1 P i-1 j-1 0 for i 1 i n i A i-1 i-1 0 for k 1 k n k for i 1 i n i for j 1 j n j if A i-1 k-1 A k-1 j-1 A i-1 j-1 A i-1 j-1 A i-1 k-1 A k-1 j-1 P i-1 j-1 k 3. Bài toán tìm bao đóng chuyển tiếp transitive closure Trong một số trường hợp ta chỉ cần xác định có hay không có đường đi nối giữa hai đỉnh i j bất kỳ. Giải thuật Floyd có thể đặc biệt hoá để giải bài toán này. Bây giờ khoảng cách giữa 146 Cấu trúc dữ liệu Chương V Đồ thị i j là không quan trọng mà ta chỉ cần biết i j có nối nhau không do đó ta cho C i j 1 true nếu i j được nối nhau bởi một cạnh ngược lại C i j 0 false . Lúc này mảng A i j không cho khoảng cách ngắn nhất giữa i j mà nó cho biết là có đường đi từ i đến j hay không. A gọi là bao đóng chuyển tiếp của đồ thị G có biểu diễn ma trận kề là C. Giải thuật Floyd sửa đổi như trên gọi là giải thuật Warshall. int A n n C n n void Warshall int i j k for i 1 i n i for j
