Finding shortest path from a node to any node of a particular type [closed]

Question

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is to find the shortest path from A to any such node, if it exists. This can be achieved by doing a breadth first search which would give the shortest distance between A and the desired node if it exists. Given that the graph can be pretty dense, what could be a better algorithm to achieve this? Both memory and time taken for the search are to be kept in mind while designing this.

If such queries could be optimized by doing some pre-processing while the graph is built, such additional hit on performance could be acceptable (not memory though).

Answer 1

Reduction to standard shortest path in a weighted graph

As indicated in comments, your question is not to clear about what is constant and what changes, and when, in your problem.

So, I am proposing an answer that can meet this fuzziness.

You extend your graph with new nodes which I am calling type-nodes. There is one type-node noted $N_t$ for each type $t$ of node you are considering.

You add edges from each node $X$ of the original graph to all type-nodes corresponding to the types the node $X$ belongs to.

Given a type $t$ and a node $A$, in order to get the shortest path from $A$ to a node of type $t$, you compute the shortest path from $A$ to $N_t$ (or from $N_t$ to $A$ ... :-). Then you remove the last edge on the $N_t$ end.

There is however one glitch to worry about: no path is allowed to go through a type-node.

One way to ensure that can simply be to put a weight on edges connecting to a type node that is the same for all and has a value greater than the number of nodes in the original graph. If the weight of the minimal path found exceeds that value, it means that there is no path satisfying the query in the original graph. Of course, all other edges have unit weight.

How you find that shortest path is up to you. The literature is full with such algorithms. Just choose one that is adapted to the precise statement of your problem (which is not precise enough in the question) modified as indicated here. The same remark applies to preprocessing optimizations.

Essentially, your problem is reducible to a standard shortest path problem on a weighted graph.

An alternative solution is to reduce to standard shortest path in a directed graph. The idea is to keep all edges bidirectional, but use directed edges for type-nodes, either all directed towards their relevant type-nodes, or all directed away from it.

Answer 2

I don't have enough rep to comment, but here are some suggestions rather than a definitive answer. These algorithms assume the graph is fixed.

Let $k$ be the number of types. The number of nodes is $n$, similarly $m$ for edges.

Case 1: $k$ is acceptably small.

Strategy: Just store the info.

Preprocessing: $\mathcal{O}(k(n + m))$, Memory: $\mathcal{O}(kn + m)$, Query Time: $\mathcal{O}(1)$

Simply store the shortest distance to any type for each node. This can be done in $\mathcal{O}(k)$ space per node. The values can be obtained by running BFS $k$ times, once for each type. Let $D[v][t]$ be the distance from node $v$ to any node of type $t$, initialized to $\infty$.

For each type $t$, find the connected component of nodes of just that type, by BFS. During the BFS, keep a set (the "boundary" nodes) of all nodes of other types that are encountered. Now BFS using that set as a starting point, record the distance in $D[v][t]$ for each node encountered. Runtime is $\mathcal{O}(n + m)$ for each type $t$.

Querying: $\mathcal{O}(1)$, just look up the value in $D$.

---

Case 2: $k$ is not that small. But the graph is very dense.

Strategy: Utilize bidirectional search after graph transform.

Preprocessing: $\mathcal{O}(n + m)$, Memory: $\mathcal{O}(n + m)$

Query Time: $\mathcal{O}(n + m)$ (but possibly better in practice, see: http://en.wikipedia.org/wiki/Bidirectional_search)

We will be adding nodes / edges and transforming the undirected graph into a directed one.

Create $k$ supernodes, $S[t]$, one for each type. For edges that link different types of nodes: $e_{u,v}$ where $type(u) \neq type(v)$, create additional edges from $v$ and $u$ directly to the supernode of the other type (directed into the supernode). Next convert all the original undirected edges into two directed edges, one in each direction.

At most, we've added $n + m$ extra links and $k < n$ (assuming a node can belong to only one type) extra nodes, preserving the memory and time bounds. The transformation itself takes $\mathcal{O}(n + m)$ time. Essentially, the supernodes allow us to search in both directions, without affecting correctness. While we BFS from the starting node, we can also BFS in reverse from the supernode of the target type. This can be more efficient if the nodes originally had large degrees (big branching factor).

Querying: To find the shortest path from node $v$ to type $t$, run a bidirectional BFS from $v$ and $S[t]$. Depending on the graph, this could be significantly faster than just a BFS for very dense graphs, and will not be asymptotically slower.