Thuật toán Floyd–Warshall là một ví dụ về quy hoạch động, và được xuất bản dưới dạng hiện nay của nó bởi Robert Floyd vào năm 1962. Tuy nhiên, nó về cơ bản giống như các thuật toán trước đó được xuất bản bởi Bernard Roy vào năm 1959 và cũng bởi Stephen Warshall vào năm 1962 để tìm bao đóng chuyển tiếp của một đồ thị, và có liên quan chặt chẽ với thuật toán của Kleene (xuất bản vào năm 1956) để chuyển đổi một tự động hóa hữu hạn xác định thành một biểu thức chính quy. Định dạng hiện đại của thuật toán dưới dạng ba vòng lặp lồng nhau được mô tả đầu tiên bởi Peter Ingerman, cũng vào năm 1962. Thuật toán[sửa | sửa mã nguồn]Thuật toán Floyd–Warshall so sánh nhiều đường đi khả dĩ trong đồ thị giữa mỗi cặp đỉnh. Nó được đảm bảo để tìm tất cả các đường đi ngắn nhất và có thể làm điều này với so sánh trong một đồ thị, mặc dù có thể có cạnh trong đồ thị. Nó làm như vậy bằng cách tăng dần ước tính đường đi ngắn nhất giữa hai đỉnh, cho đến khi ước tính tối ưu. Xét đồ thị với đỉnh đánh số từ 1 đến . Hãy xem xét hàm trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ đến sử dụng các đỉnh chỉ từ tập làm điểm trung gian trong đường đi. Giờ đây, với hàm này, mục tiêu của chúng ta là tìm độ dài của đường đi ngắn nhất từ mỗi đến từng sử dụng bất kỳ đỉnh nào trong . Theo định nghĩa, đây là giá trị , mà chúng ta sẽ tìm đệ quy. Chú ý rằng phải nhỏ hơn hoặc bằng : sẽ linh hoạt hơn nếu được phép sử dụng đỉnh . Nếu thực sự nhỏ hơn , thì phải có một đường đi từ đến sử dụng các đỉnh mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh . Đường đi này có thể được phân rã thành: (1) một đường đi từ đến sử dụng các đỉnh , kế tiếp là (2) một đường đi từ đến sử dụng các đỉnh . Và dĩ nhiên, chúng phải là các đường đi ngắn nhất như vậy, nếu không chúng ta có thể làm giảm độ dài hơn nữa. Nói cách khác, chúng ta đã đến công thức đệ quy: |
