# Shortest paths between given red vertices and arbitrary blue vertices

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 ?

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)$$.