Finding shortest path from a node to any node of a particular type 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).
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 &lt; 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.