TAILIEUCHUNG - Giáo trình cấu trúc dữ liệu part 10

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

• Kỹ thuật lập trình
• cấu trúc dữ liệu
• giáo trình cấu trúc dữ liệu
• bài giảng cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp