Thuật_toán Floyd_Warshall_Thuật toán Floyd_Warshall còn được gọi là thuật_toán Floyd được Robert_Floyd tìm ra năm 1962 thuật_toán Floyd là một thuật_toán giải_quyết bài_toán đường đi ngắn nhất trong một đồ_thị có hướng dựa trên khái_niệm các Đỉnh Trung_Gian Bài_toán Xét đồ_thị có hướng có trọng_số G V E Ma_trận khoảng_cách W i j Thuật_toán Floyd_Warshall giúp xác_định tất_cả các Đường đi ngắn nhất giữa tất_cả các cặp đỉnh Định_lý Thuật_toán Floyd_Warshall cho ta Ma_trận W Wn là ma_trận Khoảng_cách nhỏ nhất của đồ_thị G Chú_thích Có_thể hiểu một_cách đơn_giản Để đi từ a b Bạn mất 1 quãng đường là x Thuật_toán sẽ tìm 1 đường đi gián_tiếp từ a k b và nếu đường đi này ngắn hơn đường đi trực_tiếp thì ta gán luôn giá_trị nhỏ nhất của đường đi trực_tiếp bằng đường đi gián_tiếp Thuật_toán Floyd cần formula _ 1 để giải Bài_toán đường đi ngắn nhất cho mỗi cặp đỉnh So_sánh giữa 2 thuật_toán dijkstra và Floyd_Warshall_Thuật toán Dijkstra bình_thường có 2 vòng lặp lồng nhau sẽ có Độ phức_tạp thuật_toán là formula _ 2 Thuật_toán Floyd_Warshall bình_thường có 3 vòng lặp lồng nhau sẽ có Độ phức_tạp thuật_toán là formula _ 1
Thuật_toán Floyd–Warshall