Thuật toán để tìm các đường dẫn K hàng đầu trong biểu đồ, không có các đỉnh chung, trọng số âm?

Question

Tôi đang sử dụng Bellman-Ford để tìm đường đi ngắn nhất thông qua biểu đồ có một số trọng số âm. Biểu đồ không có khả năng của các vòng và không có các kết nối hai chiều. Tôi muốn tìm đường K ngắn nhất thông qua biểu đồ, nơi các đường dẫn không có chung các nút. Có một thuật toán tôi có thể tra cứu để tìm hiểu làm thế nào để làm điều này? Thực hiện đơn giản là quan trọng hơn tốc độ vào lúc này.

Đã thêm: Cảm ơn nhận xét. Để rõ ràng, tôi đang tìm kiếm các cách K hàng đầu để nhận được từ một nút bắt đầu được chỉ định đến một nút kết thúc được chỉ định, không có nút nào khác chung. Tôi cần một tối ưu toàn cầu; tuần tự tìm kiếm các nút tốt nhất và xóa không đưa ra kết quả khả quan. Điều này một: https://en.wikipedia.org/wiki/Yen%27s_algorithm, mang lại hương vị của những gì tôi đang nói về, nhưng trong trường hợp này nó đòi hỏi chi phí cạnh phi tiêu cực và nó cũng cho phép các nút được chia sẻ.

Answer 1

Tôi nghĩ rằng vấn đề có thể được giải quyết trong việc tìm kiếm Luồng chi phí tối thiểu.

Hãy chuyển đổi đồ thị theo cách sau:

1. Thay thế mỗi nút v khác ngoài nguồn và chìm với hai nút v1 và v2 nối với nhau bằng một cạnh của cân 0 từ v1 đến v2. Các cạnh đến của v trước đây nhập vào v1 và số ra gửi đi từ v2. Với vấn đề này tương đương với việc không sử dụng các cạnh đó nhiều lần.

2. Đặt công suất 1 thành tất cả các cạnh.

Tìm một dòng chảy của giá trị K sẽ cung cấp cho bạn K con đường mà không chia sẻ một nút (vì đưa công suất lên 1 trong những cạnh mới). Vì vậy, nếu luồng này là luồng chi phí tối thiểu, bạn sẽ thấy rằng các đường dẫn K này cũng có tổng chi phí tối thiểu có thể.

Giả sử bạn không có cạnh nối nguồn và bồn rửa trực tiếp. Kiểm tra trường hợp góc đó một cách riêng biệt.