2
$\begingroup$

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?

  • 0
    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.2011-07-12

1 Answers 1

6

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.

  • 0
    @user13251: Thanks $f$or the feedback. The difference between our approaches is basically the same as between the two answers to [this question](http://math.stackexchan$g$e.com/questions/187555). I don't think it affects the complexity; it's mostly a question of whether you'd rather modify the graph or the algorithm.2012-10-22