Gợi ý cho KSPA trên đồ thị vô hướng

Question

Có một triển khai tùy chỉnh KSPA cần được viết lại. Việc triển khai hiện tại sử dụng thuật toán Dijkstra đã sửa đổi có mã giả được giải thích dưới đây. Nó thường được gọi là KSPA bằng cách sử dụng chiến lược xóa cạnh tôi nghĩ như vậy. (Tôi là một người mới trong đồ thị lý thuyết).

Step:-1. Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here. 
Step:-2. Set k = 1 
Step:-3. Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List. 
Step:-4. Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination. 
Step:-5. Delete the combination of edges chosen in the above step temporarily from the graph in memory. 
Step:-6. Re-run Dijkstra for the same pair of nodes as in Step:-1. 
Step:-7. Add the resulting path into a temporary list of paths. Paths_List. 
Step:-8. Restore the deleted edges back into the graph. 
Step:-9. Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr. 
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List). 
Step:-11. k = k + 1 Go to Step:-3, until k < N. 
Step:-12. STOP 

Như tôi hiểu các thuật toán, để có được thứ k con đường ngắn nhất, SPTS 'k-1' sẽ được tìm thấy giữa mỗi cặp nguồn-đích và 'k-1' cạnh mỗi từ một SPT sẽ được xóa đồng thời cho mọi kết hợp. Rõ ràng thuật toán này có sự phức tạp tổ hợp và làm tắc nghẽn máy chủ trên các biểu đồ lớn. Mọi người gợi ý cho tôi thuật toán của Eppstein (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf). Nhưng bài báo trắng này trích dẫn một 'digraph' và tôi không thấy một đề cập đến nó chỉ hoạt động cho digraphs. Tôi chỉ muốn hỏi folks ở đây nếu có ai đã sử dụng thuật toán này trên một đồ thị vô hướng?

Nếu không, có các thuật toán tốt (về mặt thời gian phức tạp) để triển khai KSPA trên đồ thị không bị chiếu xạ không?

Cảm ơn trước,

Answer 1

Thời gian phức tạp: O (K * (E * log (K) + V * log (V)))

Memory phức tạp của O (K * V) (+ O (E) để lưu trữ đầu vào).

Chúng tôi thực hiện một Djikstra sửa đổi như sau:

• Đối với mỗi nút, thay vì duy trì chi phí hiện nay nổi tiếng nhất của tuyến đường từ lúc khởi động nút. Chúng tôi giữ nguyên các tuyến đường K tốt nhất từ ​​nút bắt đầu
• Khi cập nhật hàng xóm của một nút, chúng tôi không kiểm tra xem nó có cải thiện đường dẫn hiện tại tốt nhất (như Djikstra không) hay không. đường dẫn hiện đã biết.
• Sau khi chúng tôi đã xử lý tuyến đường K tốt nhất đầu tiên của một nút, chúng tôi không cần tìm K tuyến tốt nhất, nhưng chỉ còn lại K-1 và sau đó là K-2. Đó là những gì tôi gọi là K '.
• Đối với mỗi nút, chúng tôi sẽ giữ hai hàng đợi ưu tiên cho độ dài đường dẫn được biết đến nhiều nhất của K '.
  • Trong một hàng đợi ưu tiên, đường đi ngắn nhất ở trên cùng. Chúng tôi sử dụng hàng đợi ưu tiên này để xác định xem K 'nào là tốt nhất và sẽ được sử dụng trong hàng đợi ưu tiên thường xuyên của Djikstra làm đại diện của nút.
  • Trong hàng đợi ưu tiên khác, đường dẫn dài nhất ở trên cùng. Chúng tôi sử dụng cái này để so sánh các đường dẫn ứng viên với đường dẫn K tồi tệ nhất.