Trình trực quan hóa thuật toán Dijkstra

Cách dùng

1. 1 Vẽ tường bằng cách click và kéo trên lưới ô; kéo điểm bắt đầu màu xanh lá hoặc điểm đích màu đỏ để di chuyển chúng.
2. 2 Nhấn Play để xem Dijkstra mở rộng dần ra từ điểm bắt đầu theo thứ tự khoảng cách.
3. 3 Dùng Maze để tạo chướng ngại vật ngay lập tức, hoặc Step để chạy từng ô một.
4. 4 Khi chạm tới đích, đường đi ngắn nhất sẽ được tô sáng màu vàng gold.

Vì sao dùng công cụ này

• Quan sát Dijkstra khám phá các ô theo thứ tự khoảng cách tăng dần — kiểu tìm kiếm chi phí đồng nhất (uniform-cost search) kinh điển.
• Trên lưới ô không trọng số, mỗi cạnh có chi phí bằng 1, nên Dijkstra tìm ra đường đi ngắn nhất.
• So sánh phạm vi khám phá rộng của nó với A*, thuật toán dùng heuristic để hướng thẳng về phía đích.
• Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải file lên.

Câu hỏi thường gặp

Trình trực quan hóa thuật toán Dijkstra là gì?

Trình trực quan hóa thuật toán Dijkstra mô phỏng quá trình tìm đường đi ngắn nhất trên lưới ô: thuật toán liên tục mở rộng từ ô chưa thăm gần nhất, khám phá dần ra xa theo khoảng cách cho tới khi chạm đích, sau đó tô sáng đường đi ngắn nhất. Bạn có thể vẽ tường và di chuyển điểm bắt đầu, điểm đích.

So sánh

Công cụ liên quan