Đường đi ngắn nhất khi không có cạnh đã cho

Question

Giả sử chúng ta có biểu đồ có trọng số G (V, E).

Đồ thị chứa N đỉnh (đánh số từ 0 đến N-1) và M hai chiều cạnh.

Mỗi cạnh (vi, vj) có postive khoảng cách d (tức là khoảng cách giữa hai đỉnh vivj là d)

Có atmost một cạnh giữa hai đỉnh và cũng có không tự lặp (ie.no cạnh kết nối một đỉnh để chính nó.)

Ngoài ra chúng tôi được cho S đỉnh nguồn và D đỉnh đích.

hãy Q được số truy vấn, mỗi truy vấn chứa một cạnh e (x, y).

Đối với mỗi truy vấn, chúng tôi phải tìm đường đi ngắn nhất từ nguồn S đến đích D, giả sử rằng cạnh (x, y) không có trong biểu đồ gốc. Nếu không có bất kỳ con đường tồn tại từ S đến D, sau đó chúng ta phải in số

ràng buộc cao 0 < = (N, Q, M) < = 25000

Làm thế nào để giải quyết việc này vấn đề hiệu quả?

Cho đến bây giờ những gì tôi đã làm được triển khai thực hiện thuật toán Dijakstra đơn giản .

Đối với mỗi truy vấn Q, mọi tôi gán (x, y) để Infinity và tìm Dijakstra con đường ngắn nhất.

Nhưng phương pháp này sẽ rất chậm như tổng thể phức tạp sẽ Q (thời gian phức tạp của con đường Dijastra Shortes) *

Ví dụ ::

N=6,M=9 
S=0 ,D=5 

(u,v,cost(u,v)) 
0 2 4 
3 5 8 
3 4 1 
2 3 1 
0 1 1 
4 5 1 
2 4 5 
1 2 1 
1 3 3 

Total Queries =6 

Query edge=(0,1) Answer=7 
Query edge=(0,2) Answer=5 
Query edge=(1,3) Answer=5 
Query edge=(2,3) Answer=6 
Query edge=(4,5) Answer=11 
Query edge=(3,4) Answer=8 

Answer 1

Đầu tiên, tính toán cây đường đi ngắn nhất từ ​​nút nguồn đến đích.

Thứ hai, lặp qua tất cả truy vấn và cắt đường đi ngắn nhất ở cạnh được chỉ định bởi truy vấn; điều này định nghĩa một vấn đề min-cut, nơi bạn có khoảng cách giữa nút nguồn và biên giới của một phân vùng và biên giới của điểm khác và đích đến; bạn có thể tính toán vấn đề này rất dễ dàng, tối đa là O(|E|).

Do đó, thuật toán này yêu cầu O(Q|E| + |V|log|V|), nhanh hơn nhiều so với giải pháp ngây thơ khi |V|log|V| > |E|.

Giải pháp này sử dụng lại tính toán của Dijkstra, nhưng vẫn xử lý từng truy vấn riêng lẻ, vì vậy có lẽ có chỗ để cải tiến bằng cách khai thác công việc đã làm trong truy vấn trước đó trong truy vấn liên tiếp bằng cách quan sát hình dạng vết cắt do cạnh tạo ra.

Answer 2

Một tối ưu hóa đơn giản: đầu tiên chạy Dijkstra trên biểu đồ hoàn chỉnh (không có cạnh nào được xóa).

Sau đó, đối với mỗi truy vấn - hãy kiểm tra xem cạnh được yêu cầu có thuộc về đường đi ngắn nhất đó hay không. Nếu không - loại bỏ cạnh này sẽ không tạo ra bất kỳ sự khác biệt nào.

Answer 3

Đối với mỗi truy vấn, đồ thị chỉ thay đổi rất ít, vì vậy bạn có thể sử dụng lại rất nhiều tính toán của mình.

tôi đề nghị các phương pháp sau đây:

1. Tính con đường ngắn nhất từ ​​S cho tất cả các nút khác (Dijkstras thuật toán nào đó cho bạn rồi). Điều này sẽ cung cấp cho bạn cây con đường ngắn nhất T.
2. Đối với mỗi truy vấn, lấy cây này, cắt tỉa cạnh (x, y) khỏi truy vấn. Đây có thể là cây gốc (nếu (x, y) không có vị trí trên cây) hoặc cây nhỏ hơn T '.
   • Nếu D là trong T ', bạn có thể đi theo con đường ngắn nhất gốc
   • Nếu không bắt đầu Dijkstra, nhưng sử dụng các nhãn bạn đã có từ T' (các đường dẫn đã nhỏ nhất) dưới dạng nhãn vĩnh viễn.

Nếu bạn chạy Dijkstra trong bước 2, bạn có thể tái sử dụng cắt tỉa một phần của cây T theo cách sau: Mỗi khi bạn muốn đánh dấu một nút vĩnh viễn (đó là một trong các nút không phải trong T ') bạn có thể đính kèm toàn bộ cây con của nút này (từ cây gốc T) vào cây đường đi ngắn nhất mới và gắn nhãn tất cả các nút của nó vĩnh viễn.

Bằng cách này bạn sử dụng lại càng nhiều thông tin càng tốt từ đường chạy ngắn nhất đầu tiên.

---

Trong ví dụ của bạn này có nghĩa là:

Tính con đường ngắn nhất cây: 0-> 1-> 2-> 3> 4> 5 (trong trường hợp này rất đơn giản)

Bây giờ giả sử chúng tôi nhận được truy vấn (1,2).

Chúng tôi prune cạnh (1,2) để lại cho chúng ta 0-> 1

Từ đó chúng tôi bắt đầu nhận được Dijkstra 2 và 3 như sau nút đánh dấu vĩnh viễn. Chúng tôi kết nối 1 đến 2 và 1 đến 3 trong cây đường đi ngắn nhất mới và đính kèm cây con cũ từ 3: -0-> 1-> 3-> 4-> 5

Vì vậy, chúng tôi có đoạn mã ngắn nhất đường dẫn chỉ với một bước bổ sung của thuật toán Dijkstras.

---

Sự đúng đắn của thuật toán sau từ tất cả các đường dẫn trong cây T là tại hầu hết chừng nào trong Graph mới từ Query (nơi mọi con đường ngắn nhất chỉ có thể là lâu hơn). Do đó, chúng tôi có thể tái sử dụng mọi con đường từ cây vẫn còn khả thi (nghĩa là không có cạnh nào bị loại bỏ).

Nếu hiệu suất rất quan trọng, bạn có thể cải thiện hiệu suất Dijkstra thông qua nhiều thủ thuật triển khai. Một điểm vào tốt cho điều này có thể là DIMACS Shortest Path Implementation Challenge.