graph - Dijkstra cho The Single-Nguồn Longest Đường dẫn

Question

Ok, tôi đăng câu hỏi này vì bài tập này:

Chúng ta có thể thay đổi thuật toán Dijkstra để giải quyết đơn nguồn vấn đề con đường dài nhất bằng cách thay đổi tối thiểu để tối đa? Nếu có thì hãy chứng minh thuật toán của bạn đúng. Nếu không, hãy cung cấp một ví dụ.

Đối với bài tập này hay tất cả mọi thứ liên quan đến thuật toán Dijkstra, tôi giả sử không có trọng lượng tiêu cực trong đồ thị dưới. Nếu không, nó không có ý nghĩa nhiều, ngay cả đối với vấn đề đường đi ngắn nhất, Dijkstra không thể hoạt động bình thường nếu cạnh tiêu cực tồn tại.

---

Ok, trực giác của tôi đã trả lời nó cho tôi:

Vâng, tôi nghĩ rằng nó có thể được sửa đổi.

Tôi chỉ

1. khởi khoảng cách mảng để MININT
2. thay đổi distance[w] > distance[v]+weight để distance[w] < distance[v]+weight

---

Sau đó, tôi đã làm một số nghiên cứu để xác minh câu trả lời của tôi. Tôi tìm thấy bài đăng này:

Longest path between from a source to certain nodes in a DAG

Trước tiên tôi nghĩ câu trả lời của tôi đã sai vì bài viết ở trên. Nhưng tôi thấy rằng có lẽ câu trả lời trong bài viết ở trên là sai. Nó trộn lẫn Sự cố đường dẫn dài nhất một nguồn với Sự cố đường dẫn dài nhất.

Cũng trong wiki của Bellman–Ford algorithm, nó nói một cách chính xác:

Thuật toán Bellman-Ford tính đơn nguồn đường đi ngắn nhất trong một digraph quân gia quyền. Đối với đồ thị chỉ có trọng số cạnh không âm, thuật toán Dijkstra nhanh hơn cũng giải quyết được vấn đề. Do đó, Bellman-Ford được sử dụng chủ yếu cho các đồ thị có trọng số cạnh tiêu cực.

Vì vậy, tôi nghĩ câu trả lời của tôi là chính xác, đúng không? Dijkstra thực sự có thể là Các nguồn duy nhất Vấn đề đường dẫn dài nhất và các sửa đổi của tôi cũng đúng, phải không?

Answer 1

Không, chúng ta không thể - hoặc ít nhất, không có giảm/sửa đổi đa thức được biết đến - longest path problem là NP-Hard, trong khi Dijkstra chạy trong thời gian đa thức!

Nếu chúng ta có thể tìm thấy một modfication để dijsktra để trả lời vấn đề lâu nhất đường dẫn trong thời gian đa thức, chúng ta có thể lấy được P=NP

Nếu không, sau đó cung cấp một phản ví dụ.

Đây là nhiệm vụ rất xấu. Ví dụ truy cập có thể cung cấp một sửa đổi cụ thể là sai, trong khi có thể có một sửa đổi khác nhau đó là OK.
Sự thật là chúng ta không biết nếu vấn đề con đường dài nhất có thể giải được trong thời gian đa thức hay không, nhưng giả định chung là - nó không phải là.

---

về chỉ cần thay đổi các bước thư giãn:

 A 
    /\ 
     1 2 
    / \ 
    B<--1---C 
edges are (A,B),(A,C),(C,B) 

Dijkstra từ A đầu tiên sẽ chọn B, và sau đó B là không bao giờ có thể truy cập - vì nó được ra khỏi bộ distances.

Ít nhất, người ta cũng sẽ phải thay đổi heap tối thiểu thành heap tối đa, nhưng nó sẽ có một ví dụ phản đối khác vì sao nó không thành công.

---

(1) có thể, có thể nếu P = NP có thể, nhưng rất khó xảy ra.

Answer 2

Có, chúng tôi có thể. Và câu trả lời của bạn gần như chính xác. Ngoại trừ một điều.

Bạn giả sử không có trọng số âm. Trong trường hợp này thuật toán của Dijkstra không thể tìm thấy đường đi dài nhất.

Nhưng nếu bạn giả sử chỉ trọng số âm, bạn có thể dễ dàng tìm thấy đường đi dài nhất. Để chứng minh tính chính xác, chỉ cần lấy giá trị tuyệt đối của tất cả các trọng số và bạn nhận được chính xác thuật toán Dijkstra thông thường với trọng số tích cực.

Answer 3

Nó hoạt động trong biểu đồ tuần hoàn theo hướng nhưng không có trong biểu đồ tuần hoàn. Kể từ khi con đường sẽ trở lại theo dõi và không có cách nào để tránh điều đó trong dijkstra của algo