1677155
Thuật toán Floyd–Warshall
https://vi.wikipedia.org/wiki?curid=1677155
Title: Thuật toán Floyd–Warshall
Trong khoa học máy tính, thuật toán Floyd-Warshall (còn được gọi là thuật toán Floyd, thuật toán Roy-Warshall, thuật toán Roy-Floyd hoặc thuật toán WFI) là một thuật toán để tìm đường đi ngắn nhất trong đồ thị có hướng đồ thị có trọng số với trọng số cạnh dương hoặc âm (nhưng không có chu trình âm). Một lần thực hiện thuật toán sẽ tìm ra độ dài (trọng số tổng hợp) của đường đi ngắn nhất giữa mọi cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường đi, có thể khôi phục các đường đi với sửa đổi đơn giản cho thuật toán. Các phiên bản của thuật toán cũng có thể được sử dụng để tìm bao đóng chuyển tiếp của quan hệ formula_1, hoặc (liên quan đến phương pháp bỏ phiếu Schulze) đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị có trọng số.
Lịch sử và tên gọi.
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.
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 formula_2 so sánh trong một đồ thị, mặc dù có thể có formula_3 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.