Thuật toán dijkstras có làm giãn các cạnh của đường đi ngắn nhất theo thứ tự không?

Question

Trong bài "Giới thiệu về thuật toán, ấn bản lần 3", bài tập 24.3-5 muốn một ví dụ rằng điều này là sai (không phải lúc nào cũng đúng). Điều đó có thể không? Trong tâm trí của tôi điều này là không thể bởi vì mọi cạnh được thoải mái tại một thời điểm khi đường dẫn đến đỉnh hiện tại đã được quyết định.

Word cho từ:

Giáo sư N. tuyên bố có bằng chứng về tính đúng đắn của thuật toán Dijkstra. Ông tuyên bố rằng thuật toán của Dijkstra làm giãn các cạnh của mọi đường đi ngắn nhất trong biểu đồ theo thứ tự chúng xuất hiện trên đường dẫn, và do đó thuộc tính thư giãn đường dẫn áp dụng cho mọi đỉnh có thể truy cập từ nguồn. Cho thấy giáo sư bị nhầm lẫn bằng cách xây dựng một đồ thị có hướng dẫn mà thuật toán của Dijkstra có thể thư giãn các cạnh của một con đường ngắn nhất ra khỏi trật tự.

Answer 1

Tôi nghĩ rằng cụm từ then chốt trong cách diễn đạt là thuật toán Dijkstra "thư giãn các cạnh của mỗi con đường ngắn nhất trong đồ thị dưới ..."

Điều đó một mình là một lời nói dối nếu có nhiều con đường ngắn nhất của cùng một chi phí.

Xem xét biểu đồ này: A -> B, A -> C, B -> D, C -> D. Nguồn là A và Đích là D. Mỗi cạnh trọng số là 1. Có hai đường dẫn từ A đến D, một qua B và một đến C. Tuy nhiên một cạnh B-> D hoặc C-> D không bao giờ được thư giãn.

Vẫn không thuyết phục vì dijkstra chấm dứt trước khi đánh giá cạnh khác vào D? Toss trong một cạnh thêm D-> E và thiết lập các điểm đến E. Đường đi từ A-> D đến B có cùng chi phí như A-> D đến C và chúng rẻ hơn cả chi phí từ A-> E. Tuy nhiên bạn sẽ không bao giờ thư giãn cạnh thứ hai vào D vì thuật toán chỉ làm giãn các cạnh tới đỉnh mà nó chưa biết đường đi ngắn nhất tới.

Answer 2

Tạo một cạnh, trọng lượng ba, đạt đến đích. Bây giờ thêm một đường dẫn bao gồm một số điểm dừng, tổng trọng lượng ít hơn ba, mà cũng đạt đến đích. Khi bạn thư giãn nguồn gốc, bạn sẽ tô màu nút đích là ba, đó là sai. Bạn phải tiếp tục thư giãn tất cả các nút gần hơn (min biết đường dẫn đến đích) cho đến khi thiết lập đó là sản phẩm nào. Chỉ khi đó bạn mới có thể chắc chắn thuật toán của D đã cho bạn câu trả lời chính xác.

Tra cứu thuật toán A * để vui hơn.

Answer 3

Vấn đề là kết luận không tuân theo các cơ sở và để xây dựng một ví dụ. SSSP tìm thấy tất cả đường đi ngắn nhất. Không có lý do gì mà các đường đi ngắn nhất cần được tìm thấy theo thứ tự nghiêm ngặt. Hãy xem xét một biểu đồ cây. Tất cả các đường dẫn cũng ngắn nhất. Bây giờ, nếu chúng ta thư giãn gốc, thì không có thứ tự đặc biệt nào trên các cạnh. Nhưng giả sử bạn thậm chí áp đặt một. Sau đó, sau khi thư giãn nút không phải gốc gần nhất, bạn có thể có một loạt các cạnh thực sự dài đến tầng thứ hai. Người hàng xóm gần nhất gần nhất có thể có một loạt các cạnh ngắn thực sự ngắn tới phần đó của tầng thứ hai. Trong trường hợp đó, bạn sẽ thư giãn các cạnh góp phần vào tổng chiều dài đường đi SHORTER so với các mép khác bạn đã thư giãn, vì bạn luôn luôn thư giãn NODES, không cạnh, theo thứ tự ngắn nhất.

Answer 4

Hãy xem xét đồ thị được chỉ dẫn sau: (A, B), (A, C), (B, D), (C, D), (D, E) với các trọng số cạnh w (A, B) = 1 , w (A, C) = 1, w (B, D) = 0, w (C, D) = 0, w (D, E) = 1.Các đỉnh nguồn là A. Một hoán vị có thể có của các cạnh thoải mái thuật toán Dijkstra là (A, B), (A, C), (B, D), (D, E), (C, D). Bên cạnh đó, A.d = 0, B.d = 1, C.d = 1, D.d = 1, E.d = 2 sau khi thực hiện thuật toán Dijkstra. Có hai đường đi ngắn nhất từ ​​A đến E, một là ABDE và một là ACDE.Sự mâu thuẫn với con đường thứ hai, cạnh (C, D) phải luôn luôn được nới lỏng trước (D, E).

Answer 5

Xem xét biểu đồ:

A--->B A--->C B--->C C--->D 

và để cho mỗi cạnh có trọng lượng 0.

thuật toán Dijkstra có thể thư giãn các cạnh theo thứ tự

(A,C) (A,B) (C,D) (B,C) 

Đồ thị có hai con đường ngắn nhất từ A đến D, cả hai chi phí 0.

A-->B-->C-->D or A-->C-->D 

Các cạnh của đường đi ngắn nhất {A -> B -> C -> D} được giải phóng theo thứ tự vì (B, C) được thoải mái SAU (C, D).