Shortest paths between given red vertices and arbitrary blue vertices

Question

Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the graph. I have tried using Dijkstra algorithm with source the given red vertex, then finding the shortest path among all shortest paths, but I have to answer many queries for the red vertices and this method proved inefficient. Are there any more efficient algorithms for this problem ?

Answer 1

I assume no negative weights in this solution (since you stated Dijkstra). My solution also uses Dijkstra. Let $G'$ be the graph resulting from $G$ by contracting all the blue vertices into one vertex - which means, remove all blue vertices in the graph and add one blue vertex $b$, and for each edge between a red vertex $u$ and a blue vertex $v$, add an edge between $u$ and $b$.

Claim. A shortest path from a red vertex $u$ to a blue vertex in $G$ has the same length as a short $u$ to $b$ in $G'$.

Proof. Since the graph does not have negative weights, a shortest path can always be replaced with another shortest path with only the last vertex blue (every thing after this vertex are edges with weight 0). Now there is a one-to-one correspondence between shortest paths in both graphs, since inner-vertices on the path can be translated without change and the last edge of the path in $G$ corresponds to an artificial edge to $b$ in $G'$ with the same weight.

Now since the graph is undirected, a shortest path from $u$ to $v$ is a shortest path from $v$ to $u$ (in case of directed graphs we can do this by inverting the graph) and hence, instead of running Dijkstra for each query from a red vertex $v$, run one Dijkstra as preprocessing from $b$ and for each query vertex $v$ answer $d_{G'}(b, v)$.