30/09/2018, 18:32
Sử dụng các thuật toán đồ thị
Hiện tại mình đang học các loại thuật toán : DFS, BFS, Floyd, Dijkstra . Nói chung thì cũng đã hiểu về các loại thuật toán này rồi nhưng mình vẫn băn khoăn không biết với những bài toán nào thì dùng loại thuật toán nào cho tối ưu.
Xin cảm ơn!!!
Bài liên quan
Mình nghĩ Dijkstra là nhanh nhất vì bản chất của nó là dùng quy hoạch động.
Còn những thuật toán còn lại thì dễ đọc và dễ hiểu hơn.
DFS,BFS là thuật toán tìm đường đi với cạnh không có trọng số, chiều dài là số đỉnh (cạnh) đi qua. Thường dc dùng để tìm đường ngắn nhất trên ma trận ô vuông, Cây …
Floyd, Dijkstra tìm đường đi ngắn nhất trên đồ thị có trọng số.
Floyd có phải là quy hoạch động không bạn?
Không biết ưu và nhược điểm của floyd và dijkstra là gì?
Theo mình hiểu thì quy hoạch động là tính bài toán lớn bằng một bộ dữ liệu các bài toán con. Mình nghĩ floyd là quy hoạch động đấy. Tính điểm đích bằng cách tính các điểm ở giữa điểm đầu và đích.
Thế còn dijkstra thì sao? Sao mình nó kiểu như BFS
Dijkstra mà thấy giống BFS là học đúng rồi đó
BFS = Dijkstra với tất cả các trọng số bằng nhau.
Có đúng không vậy. Ý mình nói tới cách mà nó duyệt qua các đỉnh thì giống nhau