Dijkstra vs A*
Dijkstra vs A* compared — heuristics, speed, optimality and use cases, with interactive pathfinding visualizers.
Dijkstra finds shortest paths from a source to every node; A* adds a heuristic that aims at a single goal, exploring far fewer nodes. A* with a good heuristic is Dijkstra, only smarter about direction.
Dijkstra vs A* at a glance
| Dijkstra | A* | |
|---|---|---|
| Heuristic | None | Yes (estimate to goal) |
| Target | All nodes | One goal |
| Nodes explored | More | Fewer |
| Optimal | Yes | Yes (admissible heuristic) |
When to use Dijkstra
Use Dijkstra for shortest paths to all nodes or when no good heuristic exists.
When to use A*
Use A* for point-to-point pathfinding where you can estimate distance to the goal.
Tools for Dijkstra & A*
Trình trực quan hóa thuật toán Dijkstra
Trực quan hóa tìm đường Dijkstra trên lưới ô — vẽ tường, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình tìm kiếm. Hoạt động ngay trên trình duyệt.
Mở công cụTrình trực quan hóa thuật toán tìm đường A*
Tìm đường A* tương tác trên lưới ô vuông với heuristic Manhattan — vẽ tường chắn, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình tìm kiếm. Chạy hoàn toàn trên trình duyệt.
Mở công cụTrình trực quan Tìm kiếm theo chiều rộng (BFS)
Tìm kiếm theo chiều rộng tương tác trên lưới ô — vẽ tường, di chuyển điểm bắt đầu/đích, sinh mê cung, xem từng bước mở rộng theo từng lớp. Chạy ngay trên trình duyệt.
Mở công cụTrình tạo mê cung
Trình tạo mê cung có hoạt ảnh bằng thuật toán chia đệ quy (recursive division) — xem từng bước dựng tường, điều chỉnh tốc độ, tạo mê cung mới. Kết hợp tốt với các trình trực quan hóa thuật toán tìm đường. Chạy hoàn toàn trên trình duyệt.
Mở công cụDijkstra vs A*
Thuật toán chia đệ quy tạo mê cung như thế nào?
Nó bắt đầu với một vùng trống, sau đó chia đệ quy mỗi khoang bằng một bức tường thẳng có một khe hở ngẫu nhiên, lặp lại cho đến khi các khoang quá nhỏ để chia tiếp.
Mê cung "hoàn hảo" là gì?
Một mê cung có đúng một đường đi giữa hai ô bất kỳ — không có vòng lặp và không có vùng bị cô lập. Thuật toán chia đệ quy luôn tạo ra mê cung hoàn hảo.
Tôi có thể giải mê cung này không?
Có — sao chép bố cục sang các trình trực quan hóa BFS, Dijkstra hoặc A* (cùng chung lưới ô vuông) để xem thuật toán tìm đường đi qua nó.
Còn những thuật toán tạo mê cung nào khác?
Recursive backtracker (DFS ngẫu nhiên hóa), Prim's, Kruskal's, Wilson's và Eller's — mỗi thuật toán tạo ra mê cung với kết cấu hình ảnh khác nhau.