Finding the shortest path between any two nodes belonging to two disjoint subsets of a graph

Question

There is an undirected graph in which every node is assigned some color. I have to find the shortest path from any blue colored node to any red colored node. (Other colors may also exist in the graph and although it doesnt matter but it is not known how many colors are there.) How can I do it in polynomial time?

Answer 1

As a hint, add two new nodes to the graph- call them s and t. Connect s to each blue node with an edge of cost 0 and each red node to t with an edge of cost 0. Then find the shortest path from s to t.

Hope this helps!