Bài 14: Thuật toán Floyd-Warshall

Tham khảo Video sau đây :

1.Định nghĩa

• Thuật toán Floyd dùng để tìm ra đường đi ngắn nhất giữa tất cả các cặp đỉnh bất kỳ của một đồ thị G với các cạnh có trọng số dương

• Dữ liệu nhập cho thuật toán là ma trận trọng lượng D

2.Thuật toán

• Khởi đầu với ma trận trọng số D

• Thực hiện n lần lặp trên D. Sau bước lặp thứ k, D[i,j] chứa độ dài đường đi ngắn nhất từ đỉnh i tới đỉnh j mà chỉ đi qua các định có trọng số không vượt quá k

3.Code thuật toán

Tham khảo Video sau đây :