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?
Best Answer
How about this: In Dijkstra's algorithm, instead of storing one distance for each vertex, store two distances that record the minimal distance to the vertex via paths with even and odd numbers of green vertices, respectively. Maintain a set of unvisited distances (instead of vertices), and treat each distance separately for purposes of finding the minimal distance in the unvisited set, visiting it and marking it as visited. Terminate when the distance to the destination vertex with an odd number of green vertices is the minimal distance in the unvisited set.