Thuật toán Eppstein và thuật toán của Yen cho k đường đi ngắn nhất

Question

Tôi đang cố gắng hiểu chính xác các thuật toán này hoạt động như thế nào, nhưng tôi không thể tìm thấy lời giải thích đơn giản. Tôi sẽ đánh giá rất cao nếu ai đó có thể cung cấp hoặc chỉ cho tôi mô tả về các thuật toán này dễ hiểu hơn mô tả trong các bài báo gốc. Cảm ơn.

Answer 1

Trước hết hãy để tôi cung cấp cho bạn các liên kết đến các giấy tờ bạn đang nói đến.

Eppstein của giấy: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

Yên giấy: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

Dưới đây là lời giải thích của tôi về thuật toán Yên:

thuật toán Yên sử dụng hai danh sách, tức là danh sách A (đường đi ngắn nhất vĩnh viễn từ nguồn tới đích - được sắp xếp theo thứ tự thời gian) và danh sách B (đường dẫn ngắn nhất dự kiến ​​/ ứng cử viên). Lúc đầu, bạn phải tìm đường đi ngắn nhất đầu tiên từ nguồn đến đích bằng cách sử dụng bất kỳ thuật toán đường dẫn ngắn nhất phù hợp nào (ví dụ: Dijkstra). Sau đó, Yên khai thác ý tưởng rằng các đường đi ngắn nhất k-th có thể chia sẻ các cạnh và đường phụ (đường đi từ nguồn tới bất kỳ nút trung gian nào trong tuyến) từ (k-1) - đường đi ngắn nhất. Sau đó, bạn phải thực hiện (k-1) đường đi ngắn nhất và làm cho mỗi nút trong tuyến đường không thể truy cập lần lượt, tức là chà ra cạnh cụ thể đi đến nút trong tuyến đường. Khi nút không thể truy cập được, hãy tìm đường đi ngắn nhất từ ​​nút trước đến đích. Sau đó, bạn có một tuyến đường mới được tạo ra bằng cách nối thêm đường dẫn con chung (từ nguồn đến nút trước của nút không truy cập được) và thêm đường đi ngắn nhất từ ​​nút trước đến đích. Tuyến đường này sau đó được thêm vào danh sách B, miễn là nó chưa xuất hiện trong danh sách A hoặc danh sách B trước đó. Sau khi lặp lại điều này cho tất cả các nút trong tuyến đường, bạn phải tìm tuyến đường ngắn nhất trong danh sách B và di chuyển đến danh sách A. Bạn chỉ cần lặp lại quy trình này cho số lượng K mà bạn có.

Thuật toán này có độ phức tạp tính toán của O (kn^3). Vui lòng đọc bài báo để biết thêm chi tiết.

Thuật toán như sau:

G = Adjacent Matrix of the Network 
Initialize: 
A_1 = shortest-path from source to destination 
Glocal ← Local copy of G 
for k = 2 → K do 
for i = 1 → [len(A_(k−1)) − 1] do 
    Current Node ← A_(k−1) [i] 
    Ri ← Sub-path (root) from source till current node in A_(k−1) 
    for j = 1 → k − 1 do 
    Rj ← Sub-path (root) from source till current node in A_j 
    if Ri == Rj then 
    Next Node ← Aj [i+1] 
    Glocal(Current Node, Next Node) ← infinity 
    Current Node ← unreachable 
    end if 
    end for 
    Si ← Shortest-path from current node till destination 
    Bi ← Ri + Si 
end for 
A_k ← Shortest-path amongst all paths in B 
Restore original graph: Glocal ← Local copy of G 
end for 

Thật không may, tôi đã không sử dụng một Eppstein như thuật toán Yên là tối ưu cho vấn đề của tôi.

Hy vọng điều này sẽ hữu ích. Chúc mừng.

=====

Edit:

hãy có một cái nhìn tại wikipedia entry là tốt. Nó có một ví dụ tốt đẹp.

=====

Edit:

Tôi đã tìm thấy một số hiện thực trong C. Các liên kết như sau:

Eppstein implementation và Loading Graph for Eppstein.

Nếu bạn quan tâm, có một số lazy version của Eppstein.Các liên kết như sau:

Lazy Eppstein by Jimenez and Marzal

=====

Edit:

Just another link. Điều này chứa một số triển khai (C/C++).

=====

Edit:

Tôi đã tìm thấy một good explanation của thuật toán Eppstein của.