# Shortest Path with odd number of “Green” vertices

Suppose I have a directed graph with non-negative edge weights. In addition, each vertex is either "green" or "red". Assume that my source and destination vertices are red.

Given all of that, how do I find the shortest path with an odd number of green vertices?

-
Do you have any extra conditions on the graph? Many such graphs don't have any path with odd number of vertices... –  N. S. Jul 12 '11 at 14:12
If no path is possible, then I'm fine with getting some result that indicates as much. For example, an empty path, or an infinite distance. –  user13251 Jul 12 '11 at 17:29