CODEWITHSUNDEEP
algorithmlanguage-agnosticgraph-theory
Roy
Roy

Reputation: 867

Finding a path with minimum number of red vertices in a graph

Let G=(V,E) be an undirected graph, s and t are two vertices in V. Each edge of the graph is colored either red or blue. I need to find an algorithm that finds a path between s and t that has minimal number of red edges in it.

I thought about the following algorithm: A modified BFS algorithm

For each vertex we will use an extra field called "red level" which will indicate the minimal number of red edges on the path from s to this vertex. Once we discovered a new vertex we will update its red level field. If we are trying to explore a vertex that was already discovered, if the red level of this vertex is larger than then the current red level , than we delete this vertex from the BFS tree and insert it as a child of the vertex whose children we are now exploring, and so on. The desired path is the one connecting s and t in the BFS tree in the end of the algorithm run.

I'm trying now to prove that this algorithm is correct but with little success. I'm also not sure whether it is in fact correct. Any hints/ideas?

Upvotes: 2

Views: 1932

Answers (2)

oronlaor
oronlaor

Reputation: 1

The algorithm is, unfortunately, incorrect. Take the following graph: G = (V,E) ; V = {s, a, b, c, d, e, t} ; E = { (s,a), [s,b], [s,d], (a,b), [b,c], [d,e], (c,t), (e,t) } ;

(For convenience, I marked (,) for a blue undirected edge, and [,] for a red one)

Suppose the algorithm chooses to explore 'b' before 'a'. When we're done with 's', we'll have 'a' with red-level 0, and 'b' and 'd' with red-level 1. On exploring from 'd' we'll have 'e' with red-level 2. Now we explore from 'b': 's' and 'a' remain unchanged, but 'c' gets a red-level 2. Next we explore 'a' (according to BFS!), and it changes the parent of 'b' to be 'a', and the red-level of 'b' to be 0. Notice that on this point - that path from 's' to 'c' is correct, but the red-level on 'c' is not - it supposed to be 1 instead to 2. Now, we keep going and we ecplore from 'e' (we're done with 's' and its immediate children 'a', 'b', and 'd'): we discover 't' with the edge (e,t), so 't' gets a red-level 2. The edge (e,d) changes nothing. Now we get to the cool part - exploring from 'c': The edge (c,b) changes nothing, but what about the edge (c,t)? 't' has already been discovered (from 'e'), so according to your algorithm we only change something if there is a difference in red-level. But there isn't, because the red-level of 'c' is 2 (incorrectly!). So the parent of 't' remains 'e', and the path from 's' contains 2 red edges, while THERE IS a path from 's' to 't' that only contains 1 red edge: s -> a -> b -> c -> t

Upvotes: 0

angelatlarge
angelatlarge

Reputation: 4150

I think it is correct: essntially you are doing Dijkstra's algorithm with weights for red edges being very large, and weights for blue edges being very small or zero.

Upvotes: 6

Related Questions