- Điểm trung gian hiện tại
- Đã làm điểm trung gian
- Cặp được rút ngắn
- Đường đi
Thuật toán Floyd–Warshall
Từ mỗi thị trấn đến mọi thị trấn khác xa bao nhiêu? Floyd–Warshall trả lời một lần cho tất cả, với một bảng và ba vòng lặp lồng nhau. Mỗi vòng cho phép thêm một đỉnh làm điểm trung gian trên đường đi và hỏi, với mọi cặp, đi vòng qua đỉnh đó có ngắn hơn không. Đi từng bước để xem bảng được điền và các khoảng cách giảm xuống. Nhấn Phát để xem bảng được điền dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Bảng chứa khoảng cách ngắn nhất tìm được đến lúc đó giữa mọi cặp đỉnh; số trên mỗi cạnh là độ dài của cạnh. Mỗi vòng cho phép thêm một đỉnh làm điểm trung gian trên đường đi, và mỗi bước cho thấy một cặp được rút ngắn nhờ đi qua đỉnh đó. Nhấp vào một đỉnh để chọn làm điểm xuất phát; chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để xem đường đi ngắn nhất giữa hai đỉnh ở cuối. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng điều khiển đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Theo dõi bảng: hàng và cột của điểm trung gian hiện tại được tô màu, và mỗi bước ghi một khoảng cách ngắn hơn.
- Chọn điểm xuất phát và đích để xem đường đi ngắn nhất giữa chúng ở cuối. Đồ thị mới tạo một đồ thị khác để thử.
Floyd–Warshall hoạt động thế nào
Lập một bảng với mỗi đỉnh một hàng và một cột. Điền 0 trên đường chéo, độ dài cạnh ở chỗ hai đỉnh được nối với nhau, và vô cùng ở mọi chỗ khác. Sau đó lần lượt lấy từng đỉnh k làm điểm trung gian có thể dùng. Với mỗi cặp i, j, so sánh khoảng cách từ i đến j trong bảng với khoảng cách từ i đến k cộng khoảng cách từ k đến j, và giữ giá trị nhỏ hơn. Sau đỉnh cuối cùng, mỗi ô là khoảng cách ngắn nhất giữa hai đỉnh của nó.
Vì sao nó đúng
Sau vòng của k, bảng chứa, với mọi cặp, đường đi ngắn nhất có tất cả điểm trung gian nằm trong số các đỉnh đã xử lý. Vòng của đỉnh tiếp theo chỉ cần quyết định đỉnh đó có giúp ích không: đường đi ngắn nhất qua nó là đường đi ngắn nhất đến nó cộng đường đi ngắn nhất từ nó, cả hai đều đã có trong bảng. Cách dựng một lời giải lớn từ những lời giải nhỏ đã tìm được như vậy gọi là quy hoạch động. Khi có cạnh âm, nó vẫn đúng, và một số âm trên đường chéo cho thấy có chu trình âm.
Câu hỏi thường gặp
Thuật toán Floyd–Warshall là gì?
Một thuật toán tìm khoảng cách ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số. Nó giữ một bảng khoảng cách và, lần lượt với từng đỉnh, kiểm tra xem đi qua đỉnh đó có làm cặp nào ngắn hơn không.
Floyd–Warshall nhanh đến đâu?
Nó có ba vòng lặp lồng nhau trên n đỉnh, nên khối lượng công việc tăng theo n³, và bảng cần n² ô. Như vậy là ổn với đồ thị vài trăm đỉnh. Với đồ thị lớn và thưa, chạy thuật toán Dijkstra từ mọi đỉnh sẽ nhanh hơn.
Floyd–Warshall có xử lý được cạnh âm không?
Có, miễn là không có chu trình âm. Nếu có, một ô nào đó trên đường chéo sẽ thành số âm, và đó là cách Floyd–Warshall phát hiện chu trình âm.
Làm sao lấy được đường đi, chứ không chỉ khoảng cách?
Giữ thêm một bảng thứ hai ghi đỉnh kế tiếp trên đường từ i đến j. Mỗi khi một cặp ngắn hơn nhờ đi qua k, chép đỉnh kế tiếp từ i hướng về k. Lần theo bảng đó từ i đến j sẽ ra đường đi.
Đồ thị của tôi có bị gửi đi đâu không?
Không. Đồ thị được tạo và bảng được điền ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa