[Solved]: Dijkstra's Algorithm with different color nodes

Problem Detail: 

You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to determine if a colorful path exists, and if so, find one that contains a minimum number of white nodes.

Im not sure how to get started on this. Any help is greatly appreciated!

Asked By : Eric

Answered By : Yuval Filmus

Expanding on hengxin's idea, in order to find whether such a path exists, go over all choices of two nodes $x,y$, one red and the other blue, and see if there are paths $s \leadsto x \leadsto y \leadsto t$. In order to find the one containing the minimum number of white nodes, assign weight 1 to edges entering white nodes, and weight 0 to all other edges. The weight of a path is now the number of white nodes. Go over all possible choices of $x,y$, and calculate the minimum-weight path $s\leadsto x\leadsto y\leadsto t$; choose $x,y$ that minimize that weight.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33056