Đường vòng tuần hoàn dài nhất trong biểu đồ không có trọng số trực tiếp

Question

Thuật toán nào có thể được sử dụng để tìm đường đi dài nhất trong biểu đồ tuần hoàn không có trọng số?

Answer 1

Dynamic programming. Nó cũng được tham chiếu trong Longest path problem, cho rằng đó là một DAG.

Các mã sau đây từ Wikipedia:

algorithm dag-longest-path is 
    input: 
     Directed acyclic graph G 
    output: 
     Length of the longest path 

    length_to = array with |V(G)| elements of type int with default value 0 

    for each vertex v in topOrder(G) do 
     for each edge (v, w) in E(G) do 
      if length_to[w] <= length_to[v] + weight(G,(v,w)) then 
       length_to[w] = length_to[v] + weight(G, (v,w)) 

    return max(length_to[v] for v in V(G)) 

Answer 2

Chừng nào đồ thị là mạch hở, tất cả các bạn cần làm là phủ nhận các trọng cạnh và chạy bất kỳ thuật toán ngắn nhất con đường.

EDIT: Rõ ràng, bạn cần một thuật toán đường dẫn ngắn nhất hỗ trợ trọng số âm. Ngoài ra, thuật toán từ Wikipedia dường như có độ phức tạp thời gian tốt hơn, nhưng tôi sẽ để lại câu trả lời của tôi ở đây để tham khảo.

Answer 3

Wikipedia có một thuật toán: http://en.wikipedia.org/wiki/Longest_path_problem

Hình như họ sử dụng trọng số, nhưng nên làm việc với trọng số tất cả các thiết lập để 1.

Answer 4

có thể được giải quyết bằng phương pháp đường găng:
1. tìm một trật tự topo
2. tìm đường dẫn quan trọng
xem [Horowitz 1995], Nguyên tắc cơ bản về cấu trúc dữ liệu trong C++, Science Science Press, New York.

Chiến lược tham lam (ví dụ Dijkstra) sẽ không hoạt động, bất kể: 1. sử dụng "max" thay vì "min" 2. chuyển đổi trọng số dương thành âm 3. cho số M rất lớn và sử dụng M-w làm trọng số.