4
$\begingroup$

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 ?

$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.