Có một đồ thị vô hướng trong đó mỗi nút được gán một số màu. Tôi phải tìm đường đi ngắn nhất từ bất kỳ nút màu xanh nào đến bất kỳ nút màu đỏ nào. (Màu sắc khác cũng có thể tồn tại trong biểu đồ và mặc dù nó không quan trọng nhưng nó không được biết có bao nhiêu màu sắc.) Làm thế nào tôi có thể làm điều đó trong thời gian đa thức?Tìm đường đi ngắn nhất giữa hai nút bất kỳ thuộc hai tập con rời nhau của biểu đồ
Như một gợi ý, thêm hai nút mới vào biểu đồ, gọi chúng là s và t. Kết nối s với mỗi nút màu xanh với một cạnh của chi phí 0 và mỗi nút màu đỏ để t với một cạnh của chi phí 0. Sau đó tìm đường đi ngắn nhất từ s đến t.
Hy vọng điều này sẽ hữu ích!
cảm ơn, đây thực sự là giải pháp. – anirudh
Đa thức cả hai để thêm các nút s và t và để tìm đường đi ngắn nhất giữa chúng (ví dụ: với Dijkstra), do đó đa thức. – pvoosten
@ lbp Có rất nhiều cách dễ dàng để giải quyết nó trong thời gian đa thức, bạn có thể làm Floyd-Warshall và tìm cặp (màu xanh, đỏ) với khoảng cách tối thiểu. Bạn có thể làm Dijkstra | red | * | màu xanh | thời gian, rất kém hiệu quả, và vẫn là đa thức. Nhưng câu trả lời này cho một cách hiệu quả, không chỉ đa thức. – sdcvvc
Tôi chắc chắn thuật toán Dijkstra có thể được sử dụng theo cách nào đó để giải quyết vấn đề này, nhưng tôi chưa thể tìm ra cách. – anirudh