Chuyển tới nội dung chính
Z

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.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

Mã giả

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

Thuật toán Dijkstra là gì?

Thuật toán Dijkstra tìm đường đi ngắn nhất từ một node bắt đầu tới tất cả các node khác trong đồ thị có trọng số với các cạnh không âm, luôn mở rộng node chưa thăm gần nhất trước tiên.

Độ phức tạp thời gian của thuật toán Dijkstra là bao nhiêu?

Với hàng đợi ưu tiên dạng binary-heap, độ phức tạp là O(E log V), trong đó V là số đỉnh và E là số cạnh.

Dijkstra khác BFS ở điểm nào?

Trên đồ thị không trọng số, cả hai khám phá theo cùng một cách và đều tìm ra đường đi ngắn nhất. Dijkstra tổng quát hóa BFS cho đồ thị có trọng số bằng cách sắp xếp hàng đợi biên theo tổng khoảng cách thay vì theo số bước nhảy.

Dijkstra khác A* ở điểm nào?

A* cộng thêm ước lượng heuristic về khoảng cách còn lại vào độ ưu tiên, nên nó khám phá hướng thẳng về phía đích và thường chỉ cần thăm ít node hơn nhiều mà vẫn tìm ra đường đi ngắn nhất.

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.

Tính năng

Hoạt ảnh từng bước

Xem khoảng cách tạm thời được nới lỏng và các đỉnh được chốt theo khoảng cách ngắn nhất.

Độ phức tạp

Thời gian: O((V + E) log V) với binary heap. Không gian: O(V). Chỉ áp dụng cho trọng số không âm.

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

weighted graph, source A

Output

settle nearest unvisited node, relax its edges → final shortest distances from A

Trường hợp sử dụng

  1. 1

    Đường đi ngắn nhất có trọng số

    Tìm tuyến đường chi phí thấp nhất trong đồ thị có trọng số (bản đồ, mạng lưới).

  2. 2

    Vì sao cần trọng số không âm

    Xem lý do các cạnh trọng số âm phá vỡ bất biến tham lam (hãy dùng Bellman-Ford thay thế).

  3. 3

    Nới lỏng cạnh bằng hàng đợi ưu tiên

    Hiểu cách một min-heap dẫn dắt quá trình nới lỏng cạnh.

Tóm tắt

Trình trực quan hóa Dijkstra của Zerethon mô phỏng thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn trên đồ thị có trọng số ngay trong trình duyệt của bạn, bằng cách tham lam chốt đỉnh chưa thăm gần nhất rồi nới lỏng (relax) các cạnh của nó. Với hàng đợi ưu tiên dạng binary heap, thuật toán chạy trong thời gian O((V + E) log V) và không gian O(V). Thuật toán yêu cầu trọng số cạnh không âm.

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

Tài liệu tham khảo

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa thuật toán Dijkstra chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Graph Algorithms →

So sánh

BFS vs DFS Dijkstra vs A*

Công cụ liên quan

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 trực quan hóa Tìm kiếm theo chiều sâu (DFS)

Tìm kiếm theo chiều sâu tương tác trên lưới ô vuông — 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 khám phá đào sâu. Chạy ngay trong trình duyệt.

Mở công cụ

Trình mô phỏng Bubble Sort

Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.

Mở công cụ

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Đăng ký miễn phí