Sự khác biệt giữa thuật toán DIjkstra và BellmanFord

Question

Tôi đang luận án về thuật toán đường đi ngắn nhất. Và tôi không hiểu một điều ...

Tôi đã thực hiện trực quan hóa thuật toán dijkstras. 1) Có đúng không? Hay tôi đang làm gì sai? 2) Thuật toán Bellman-Ford như thế nào? Như fas như tôi đã tìm sự khác biệt, tôi tìm thấy "Bellman-ford: ý tưởng cơ bản là rất giống với Dijkstra, nhưng thay vì chọn cạnh láng giềng khoảng cách ngắn nhất, nó chọn tất cả các cạnh láng giềng." Nhưng cũng dijkstra kiểm tra tất cả các đỉnh và tất cả các cạnh, phải không?

Answer 1

dijkstra giả định rằng chi phí của đường dẫn tăng lên theo chiều cao. cộng với việc tìm kiếm có thứ tự (sử dụng hàng đợi ưu tiên) có nghĩa là khi bạn lần đầu tiên đến một nút, bạn đã đến qua con đường ngắn nhất.

điều này không đúng với trọng số âm. nếu bạn sử dụng dijkstra với trọng số tiêu cực thì bạn có thể tìm thấy một con đường sau đó là tốt hơn so với một trước đó (vì một trọng lượng tiêu cực cải thiện đường dẫn trên một bước sau).

vì vậy trong bellman-ford, khi bạn đến một nút bạn kiểm tra để xem đường dẫn mới có ngắn hơn không. Ngược lại, với dijkstra, bạn có thể hủy các nút

trong một số trường hợp (hầu hết) dijkstra sẽ không khám phá tất cả các đường dẫn đầy đủ. ví dụ, nếu G liên kết với C thì chi phí cao hơn bất kỳ thông qua C. bellman-ford sẽ vẫn xem xét tất cả các đường dẫn thông qua G đến F (dijkstra sẽ không bao giờ nhìn vào chúng bởi vì chúng có chi phí cao hơn đi qua C). nếu nó không làm điều này nó không thể đảm bảo việc tìm kiếm vòng lặp âm.

đây là ví dụ: ở trên không bao giờ tính toán đường dẫn AGEF. E đã được đánh dấu là đã đến thăm vào thời điểm quý khách đến từ G.

Answer 2

Tôi cũng đang nghĩ như vậy thuật toán

Dijkstra giải quyết vấn đề ngắn nhất-con đường duy nhất nguồn khi tất cả các cạnh có trọng lượng không âm. Nó là một thuật toán tham lam và tương tự như thuật toán của Prim. Thuật toán bắt đầu tại đỉnh nguồn, s, nó phát triển một cây, T, cuối cùng kéo dài tất cả các đỉnh có thể truy cập từ S. Vertices được thêm vào T theo thứ tự của khoảng cách tức là, S đầu tiên, sau đó đỉnh gần S nhất, sau đó gần nhất , v.v.