Gần đây tôi đã đính kèm phiên bản thứ 3 của thuật toán Dijkstra cho đường đi ngắn nhất của nguồn đơn vào dự án của tôi.Triển khai Dijkstra nhanh nhất mà bạn biết (trong C++) là gì?
Tôi nhận thấy rằng có nhiều triển khai khác nhau khác nhau về hiệu suất và cũng thay đổi về chất lượng của kết quả trong biểu đồ lớn. Với tập dữ liệu của tôi (> 100.000 đỉnh) thời gian chạy thay đổi từ 20 phút đến vài giây. Đường đi ngắn nhất cũng thay đổi 1-2%.
Triển khai nào tốt nhất bạn biết?
EDIT: Dữ liệu của tôi là mạng lưới thủy lực, với từ 1 đến 5 đỉnh mỗi nút. Nó có thể so sánh với bản đồ đường phố. Tôi đã thực hiện một số sửa đổi cho một thuật toán đã được tăng tốc (sử dụng một danh sách được sắp xếp cho tất cả các nút còn lại) và bây giờ tìm đến kết quả tương tự trong một phần thời gian. Tôi đã tìm kiếm một điều như vậy khá lâu rồi. Tôi tự hỏi nếu thực hiện như vậy đã tồn tại.
Tôi không thể giải thích sự khác biệt nhỏ trong kết quả. Tôi biết rằng Dijkstra không phải là heuristic, nhưng tất cả các triển khai có vẻ là chính xác. Các giải pháp nhanh hơn có kết quả với đường dẫn ngắn hơn. Tôi sử dụng toán học chính xác gấp đôi.
CHỈNH SỬA 2: Tôi phát hiện ra rằng sự khác biệt trong đường dẫn tìm thấy thực sự là lỗi của tôi. Tôi đã chèn xử lý đặc biệt cho một số đỉnh (chỉ hợp lệ theo một hướng) và quên về điều đó trong việc thực hiện khác.
NHƯNG im vẫn hơn ngạc nhiên rằng Dijkstra có thể được tăng tốc đáng kể bởi sự thay đổi sau đây: Trong một thuật toán Dijkstra chung chứa một vòng lặp như:
MyListType toDoList; // List sorted by smallest distance
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
MyNodeType *node = *toDoList.first();
toDoList.erase(toDoList.first());
...
}
Nếu bạn thay đổi điều này một chút, nó hoạt động tương tự, nhưng hoạt động tốt hơn:
MyListType toDoList; // List sorted by smallest distance
toDoList.insert(startNode);
while(! toDoList.empty())
{
MyNodeType *node = *toDoList.first();
toDoList.erase(toDoList.first());
for(MyNeigborType *x = node.Neigbors; x != NULL; x++)
{
...
toDoList.insert(x->Node);
}
}
Dường như, sửa đổi này làm giảm thời gian chạy theo thứ tự không có độ lớn, nhưng là thứ tự của số mũ. Nó giảm thời gian chạy của tôi từ 30 giây xuống dưới 2. Tôi không thể tìm thấy sửa đổi này trong bất kỳ tài liệu nào. Nó cũng rất rõ ràng rằng lý do nằm trong danh sách được sắp xếp. chèn/xóa thực hiện tồi tệ hơn nhiều với 100.000 yếu tố mà với một bàn tay đầy.
ĐÁP:
Sau rất nhiều googling tôi tìm thấy bản thân mình. Câu trả lời rõ ràng là: boost graph lib. Tuyệt vời - tôi đã không tìm thấy điều này trong một thời gian. Nếu bạn nghĩ rằng không có sự khác biệt về hiệu suất giữa việc triển khai Dijkstra, hãy xem wikipedia.
Một người bạn của tôi có thể triển khai Dijkstra trong C++ trong khoảng 3 phút. Tôi đã không nghe nói về bất kỳ triển khai nhanh hơn. – jbasko
Tôi sẽ đề nghị bạn có thể muốn kiểm tra những triển khai đó ... nếu chúng đúng, tất cả chúng phải trả về cùng một đường đi ngắn nhất ... Thuật toán của Dijkstra không phải là heuristic ... – jerryjvl
Sự khác biệt trong các đường đi ngắn nhất có thể là kết quả của sử dụng phép tính chính xác gấp đôi, vì làm tròn lỗi khi tổng hợp các chuỗi dài gấp đôi. Một thứ tự tổng hợp khác có thể tạo ra các lỗi khác nhau. Bạn có thể kiểm tra việc triển khai của mình trên các số nguyên không? –