There is an undirected graph in which each node is assigned a certain color. I have to find the shortest path from any blue node to any red node. (Other colors may also exist on the chart, and although it does not matter, it is not known how many colors there are.) How can I do this in polynomial time?
As a hint, add two new nodes to the graph - call them s and t. Connect s to each blue node with a cost edge of 0 and each red node to t with a cost edge of 0. Then find the shortest path from s to t.
, !