Tôi có khoảng 70k nút và cạnh 250k và biểu đồ không nhất thiết phải được kết nối. Rõ ràng bằng cách sử dụng một thuật toán hiệu quả là rất quan trọng. Bạn đề xuất món gì?Tìm tất cả các đường đi ngắn nhất từ mọi cặp nút trên biểu đồ
Là một lưu ý phụ, tôi sẽ đánh giá cao lời khuyên về cách phân chia nhiệm vụ giữa nhiều máy - thậm chí có thể với loại vấn đề này?
Cảm ơn
Bạn có thể sử dụng Floyd-Warshall algorithm. Nó giải quyết chính xác vấn đề này.
Độ phức tạp là O (V^3).
Ngoài ra còn có Johnson's algorithm với độ phức tạp của O (V^2 * log V + VE). Cái sau cũng dễ phân phối vì nó chạy thuật toán V của Dijkstra, có thể được thực hiện song song.
Hm. Nhưng có độ phức tạp 'O (n^3)'. Nó có thể không hiệu quả lắm. – dirkgently
@dirkgently: Trên thực tế, độ phức tạp sẽ giống như O (V^2 + V * E). Đó không phải là tên lửa nhanh, nhưng bạn có thể không thể nhận được nhiều hơn nữa nếu bạn muốn kết quả đầu ra V^2. – jpalecek
@jpalecek: Tôi đã đề cập đến bài đăng gốc và Floyd Warshall nói riêng. – dirkgently
MapReduce là một thuật toán phân phối lớn cho điều này, mặc dù nó có thể là một chút cao-powered quá. Nếu bạn quan tâm đến điều đó, hãy xem this lecture hoặc có thể là blog post để lấy cảm hứng. (Trong thực tế, khi tôi được dạy MapReduce, đây là một trong những ví dụ đầu tiên.)
Đối với 250k cạnh và 70k, có vẻ như đồ thị tương đối thưa thớt, Dijkstra's algorithm chạy trong O(E + V log V) cho mỗi nút, để chạy đầy đủ thời gian (tất cả các nguồn) của O(VE + V^2 log V). Điều này sẽ đủ nhanh, nhưng những điều cần lưu ý thường áp dụng cho Dijkstra's. (Các cạnh tiêu cực.)
Bạn cũng có thể xem Johnson's algorithm nếu vấn đề của bạn có liên quan đến trọng số âm, nhưng không phải là chu kỳ âm. Cụ thể, nó cũng có thể được phân phối, vì nó có biểu đồ được chỉnh sửa lại và chạy thuật toán Dijkstra từ mỗi nút.
Các liên kết sau không hiển thị: http://en.wikipedia.org/wiki/Dijkstra's_algorithm và http://en.wikipedia.org/wiki/Johnson's_algorithm – Larry
Bạn nên đọc về cú pháp đánh dấu cho cách định dạng bài đăng của bạn. 1 anyway từ tôi. –
Đọc tại đây: http://stackoverflow.com/editing-help –
Có hai cách ngây thơ để song song vấn đề này:
1) Xác định các thành phần phụ và phân phối chúng trên các máy tính khác nhau. Độ dài đường dẫn giữa hai nút từ hai thành phần khác nhau là không xác định.
2) Tải biểu đồ trong các máy tính khác nhau và cung cấp cho mọi máy tính một danh sách các nút để tính tất cả các đường đi ngắn nhất. Kết quả cho một nút không phụ thuộc vào kết quả của một nút khác để bạn có thể song song vấn đề này.
Upside: không quá khó để thực hiện nhưng tôi sẽ chỉ làm điều đó như thế này nếu bạn phải giải quyết điều này một lần. Nếu đây là vấn đề định kỳ thì bạn có thể muốn xem xét thuật toán phân tán.
Sử dụng igraph, được viết bằng C, khá nhanh và bạn có thể sử dụng Python làm ngôn ngữ trình bao bọc.
Xem các bài báo/ấn phẩm có từ khóa sau: thuật toán tìm kiếm đồ thị được phân phối. Here 's một trong đó có thể giúp đỡ.
Có tài khoản ACM này chỉ giấy cũng như: Distributed computation on graphs: shortest path algorithms
Bạn là chính xác, đây không phải là một vấn đề bài tập về nhà, chỉ cần một dự án cho vui. Tôi đã không được coi là xấp xỉ, nhưng trong trường hợp này tôi cần phải có được con đường thực tế giữa hai nút, và không chỉ là khoảng cách. Tôi không thấy làm thế nào một xấp xỉ có thể thực sự giúp đỡ trong trường hợp này, nhưng tôi sẽ quan tâm đến nghe như thế nào nếu họ có thể. Chỉnh sửa: Đây là phản hồi cho nhận xét đã bị xóa. Oh well. – awegawef
Xin lỗi tôi đã xóa nó!Tôi chỉ hỏi nếu bạn đã cân nhắc việc giải quyết bằng cách sử dụng xấp xỉ nhưng sau đó tôi quyết định không hỏi dù bạn đã chấp nhận câu trả lời chưa. :) –
Và một xấp xỉ trong bối cảnh này sẽ là một con đường không được đảm bảo là ngắn nhất, nhưng được đảm bảo không dài hơn x% dài hơn con đường ngắn nhất. –