Find path between 2 vertices with x red vertices

1
votes

I've tried a couple of approaches and they all ended in a dead end. The question:

Given a G=(V,E) a directed unweighted graph in which every vertex is colored red or blue. Let there be vertices s and t from V. Describe an algorithm that would find a path between s and t which would hold the least red vertices. Explain the algorithm, prove it and show its complexity.

I've thought of 2 approaches and discarded both:

  1. Use an adjacency list sorted by colors (blue first red last) and run a DFS - bad idea
  2. Set the weight of each edge from a red vertex to 2 and blues to 1 and run Dijkstra - found a counterexample

I would really be happy to get some help with the right direction. I prefer NOT to get full answers but rather hits/tips.

2
algorithmgraphdirected-graph
You might think a bit more about the weights you're setting the red and blue vertices to for your second idea. Could you see why those didn't work? - giogadi
since the assignment didn't ask for the shortest path but the path with least red vertices I could create something like this: s -> b -> b -> b -> t and s-> r -> t, if i say the weight of r->t is 2 it would still be the chosen path by BFS since the total weight of the other path is 3... - Eugene Krapivin
The problem is that, there might be a case where you have to choose between 2 paths: one path with 1 red vertex (cost 2), and one path with 10 blue vertices (cost 10). Is there a way to set the costs to make it so that, no matter what, the path with the red vertex will have a higher cost? - giogadi
@nocgod You can set the weight depending on how many vertices are in the graph. - Daniel Fischer
Try red-red edges of weight 2, red-blue ones of 1, blue-blue ones of 0. - n. 1.8e9-where's-my-share m.

2 Answers

0
votes

Consider setting weight=1 for any edge that goes to a red vertex. Then show that the cost of a path from s with n red vertices is either n or n-1, depending on the color of s.

0
votes

Well I've found an answer to this question, not me but a friend of mine after I showed him the weighted way to do it.

Instead of using one queue in the BFS algorithm we will use 2 queues: one for the blue vertices and one for the red vertices.

we check what color is S and add it to the right queue, as long as queue of the blue vertices is not empty we dequeue from it and continue the regular BFS if we encounter a red vertex we enqueue it to the red queue and if we find a blue vertex we enqueue it to the blue queue. if the blue queue is empty we dequeue from the red queue.

eventually the array pi[|V|] will hold a backwards representation to vertex v with least of red vertices.

since there is no real change to the BFS algorithm and not to it's data structures the proof of correctness holds and the time complexity is O(|V|+|E|) as in BFS.

thanks for the help guys!