patternMinor
Find a path from s to t using as few red nodes as possible
Viewed 0 times
pathnodesredpossiblefewusingfindfrom
Problem
Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and t, that you pass through as few red nodes as possible.
Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.
Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.
I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.
Initial Impressions: Since |E|≥|V|, O(|E|) time would include O(|E|+|V|), which means the solution likely uses BFS or DFS. Modifying the graph such that causing the all red nodes must be forced down a directed path of some long length (after making the whole graph directed) in order to use out-of-the-box BFS seems not viable, as it would mean constructing a new graph would be along O(|E||V|) time.
Another method I toyed around with was propagating values to nodes based on the safest path to that node while doing a DFS search, but not all values were guaranteed to update.
I still want to try to solve this myself, but I'm really stuck right now. Was wondering if there were any hints I could get. There are much simpler ways of doing this if it weren't for the O(|E|) time. Djikstras with creating some edge weights would work, but wouldn't be within the time bound.
Solution
To solve this, you need to use $BFS$. But first, manipulate $G$ so that the path will always favor blue vertices.
The solution has 2 parts:
Note any such $x$ is necessarily red.
This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.
Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertex.
The solution has 2 parts:
- Use $DFS$ on blue vertices only, to find all all-blue connected components. Let's denote each such component by $v'$. Now, each blue $v \in v'$ will be "compressed" to a single vertex $u$, and an edge $(u,x)$ will be added for every $x \in N(v')$.
Note any such $x$ is necessarily red.
This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.
Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertex.
- Use $BFS$ from $s$. That length of the path to $t$ will essentially be the shortest path under the constraint of least red vertices in the path.
Context
StackExchange Computer Science Q#106337, answer score: 8
Revisions (0)
No revisions yet.