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?

  • $\begingroup$ Do you have any extra conditions on the graph? Many such graphs don't have any path with odd number of vertices... $\endgroup$ – N. S. Jul 12 '11 at 14:12
  • $\begingroup$ 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. $\endgroup$ – user13251 Jul 12 '11 at 17:29

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.

  • $\begingroup$ I'll have to think this through some more, but it looks like it might do the trick. I was secretly hoping for some algorithm that would handle more general constraints, but this might solve my immediate problem. $\endgroup$ – user13251 Jul 12 '11 at 17:32
  • $\begingroup$ I have since used something derived from this approach. I think it is cleaner, but it may be worse as far as big-O complexity is concerned. My approach basically doubles the size of the graph by having an "even" half and "odd" half. Each edge that leads to a "green" node moves you from your current half, to the opposite half. The path must then be expressed in terms of source[Even|Odd] -> dest[Even|Odd]. $\endgroup$ – user13251 Oct 22 '12 at 14:30
  • $\begingroup$ @user13251: Thanks for the feedback. The difference between our approaches is basically the same as between the two answers to this question. I don't think it affects the complexity; it's mostly a question of whether you'd rather modify the graph or the algorithm. $\endgroup$ – joriki Oct 22 '12 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.