Dijkstra - Trình tìm đường tốt nhất mọi thời đại

infoLưu ý: Hiện tại lưới đang thiết lập Trọng số đồng nhất (1) cho mọi bước nhảy. Do đó, thuật toán Dijkstra sẽ hoạt động hoàn toàn giống hệt BFS trên bề mặt Grid 2D này.

speed Tốc độ:

directionsNguyên lý hoạt động

Thuật toán Dijkstra được sinh ra để khắc phục nhược điểm của BFS: Nó có thể tìm đường ngắn nhất trên đồ thị có trọng số (ví dụ: đoạn đường nào bị kẹt xe, đoạn nào lên dốc vất vả...).

 Tại mỗi bước, nó luôn chọn đỉnh có Ước tính Đường đi Ngắn Nhất tính từ Gốc để duyệt tiếp. Tuyệt đối không chọn bừa bãi. 

Nó được lưu trữ bằng Cấu trúc dữ liệu Priority Queue (Hàng đợi Ưu tiên) / Min-Heap.

alt_routeỨng dụng thực tế

navigationGoogle Maps Base: Phiên bản nền tảng nguyên thuỷ của Google Maps GPS (nay đã nhường chỗ cho thuật toán A* nhanh hơn).
routerRouting Mạng (OSPF): Gói tin Internet tìm đường nhảy từ trạm này mạng khác sao cho tránh tắc nghẽn.

Dijkstra Algorithm

directionsNguyên lý hoạt động

alt_routeỨng dụng thực tế

chat_bubble Bình luận (0)