- Hiện tại
- Trong hàng đợi
- Cố định
- Đường đi
Thuật toán Dijkstra
Thuật toán Dijkstra tìm đường ngắn nhất từ điểm xuất phát đến mọi đỉnh khác khi các cạnh có độ dài, như đường sá giữa các thị trấn. Thuật toán lan rộng ra từ điểm xuất phát, luôn lấy đỉnh gần nhất chưa xong. Nhấp vào một đỉnh để xuất phát từ đó, chọn đích nếu muốn, rồi đi từng bước để xem hàng đợi, từng khoảng cách giảm xuống khi tìm ra đường ngắn hơn, và đường đi ngắn nhất hiện ra. Nhấn Phát để xem quá trình tìm kiếm, 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. 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 để tìm đường đi ngắn nhất đến đó. Số trên mỗi cạnh là độ dài của cạnh, số trên mỗi đỉnh là khoảng cách ngắn nhất tìm được đến lúc đó, còn hàng dưới đồ thị là hàng đợi, đỉnh gần nhất đứng đầu. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đ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ấp vào một đỉnh để chọn làm điểm xuất phát. Để tìm đường đi, chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác.
- 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 trong quá trình tìm kiếm.
- Theo dõi hàng đợi dưới đồ thị và khoảng cách trên mỗi đỉnh. Đồ thị mới tạo một đồ thị khác để thử.
Thuật toán Dijkstra hoạt động thế nào
Gán cho điểm xuất phát khoảng cách 0 và mọi đỉnh khác vô cùng, rồi đưa điểm xuất phát vào hàng đợi. Sau đó lặp lại: lấy đỉnh trong hàng đợi có khoảng cách nhỏ nhất, và đánh dấu khoảng cách đó là cố định. Với mỗi đỉnh kề chưa cố định, cộng độ dài cạnh vào khoảng cách của đỉnh đang xét. Nếu tổng ngắn hơn khoảng cách hiện có của đỉnh kề, tổng đó thành khoảng cách mới, đỉnh đang xét được ghi nhớ là đường đến đó, và đỉnh kề vào hàng đợi nếu chưa có trong đó. Khi hàng đợi rỗng, mọi đỉnh có thể tới được đều có khoảng cách ngắn nhất.
Vì sao đỉnh gần nhất đã cố định
Khi một đỉnh là đỉnh gần nhất trong hàng đợi, mọi đường khác đến nó đều phải rời phần đã xong của đồ thị qua một đỉnh nào đó trong hàng đợi, đỉnh này ít nhất cũng xa như vậy, rồi cộng thêm các cạnh không thể âm. Vì thế không đường nào khác có thể ngắn hơn. Đó cũng là lý do đích chỉ chắc chắn khi được lấy ra khỏi hàng đợi, chứ không phải khi lần đầu tới được, và vì sao thuật toán Dijkstra thất bại với cạnh âm: khi đó cần thuật toán Bellman–Ford. Khi mọi cạnh đều có độ dài 1, thuật toán Dijkstra làm đúng như tìm kiếm theo chiều rộng.
Câu hỏi thường gặp
Thuật toán Dijkstra là gì?
Một cách tìm đường đi ngắn nhất từ một đỉnh xuất phát đến mọi đỉnh khác trong đồ thị có các cạnh dài từ 0 trở lên. Thuật toán lặp lại việc lấy đỉnh gần nhất chưa xong, cố định khoảng cách của nó, và dùng các cạnh của nó để rút ngắn khoảng cách của các đỉnh kề.
Vì sao thuật toán Dijkstra không dùng được với cạnh âm?
Thuật toán cố định khoảng cách của một đỉnh ngay khi đỉnh đó gần nhất trong hàng đợi. Một cạnh âm tìm thấy sau đó vẫn có thể dẫn quay lại đỉnh ấy bằng một đường ngắn hơn, nên khoảng cách đã cố định có thể sai. Thuật toán Bellman–Ford xử lý được cạnh âm, miễn là không có chu trình có tổng âm.
Dijkstra và BFS khác nhau thế nào?
Tìm kiếm theo chiều rộng đếm số cạnh và dùng hàng đợi thường. Thuật toán Dijkstra cộng độ dài các cạnh và dùng hàng đợi ưu tiên, luôn trả về đỉnh gần nhất. Khi mọi cạnh có độ dài 1, cả hai tìm ra cùng khoảng cách.
Thuật toán Dijkstra nhanh đến đâu?
Với đống nhị phân làm hàng đợi ưu tiên, khối lượng công việc tăng theo (V + E) log V với V đỉnh và E cạnh. Với đống Fibonacci thì là E + V log V. Ứng dụng giữ hàng đợi dưới dạng danh sách đã sắp xếp, dễ hiển thị và đủ dùng cho đồ thị nhỏ.
Đồ thị của tôi có bị gửi đi đâu không?
Không. Đồ thị được tạo và tìm kiếm 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