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 $sleadsto xleadsto yleadsto t$; choose $x,y$ that minimize that weight.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33056
