1
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by David Richerby, Juho, Guy Coder, lPlant, D.W. Jul 18 '14 at 5:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I am no expert, but if the graph is dense, I would suggest breadth first search with dynamic programming. Probably good in any case. $\endgroup$ – babou Jun 29 '14 at 11:53
  • 1
    $\begingroup$ What makes you think there could be a better algorithm? $\endgroup$ – D.W. Jun 29 '14 at 13:38
  • $\begingroup$ @babou can you please elaborate on what you mean by DP + BFS? $\endgroup$ – themanwhosoldtheworld Jun 30 '14 at 11:04
  • $\begingroup$ As I said, I am no expert. For me, BFS does not necessarily remember nodes that were encountered before in another path. Of course, you do not want to process the same node twice. So you have to recognize that. This is what I consider DP, because that has to be explicit in some computational contexts, that can be construed as graph exploration (though the graph may be intentional, computable rather than given). But I guess it is implicit and always done by graph theorists. $\endgroup$ – babou Jun 30 '14 at 11:46
  • 2
    $\begingroup$ This question is still too vague. How is the graph "built"? Addition of edges? Addition of edges and vertices? Deletion, too? Something even more complicated? Do you only ask queries once the graph is finished? Are you only interested in shortest paths to a single type of vertex or to many types? Is $A$ a fixed vertex or is it part of the input to the query? $\endgroup$ – David Richerby Jul 16 '14 at 22:32
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are $n$ and $m$ ? Why do you assume $k<n$? $\endgroup$ – babou Jul 17 '14 at 22:03
  • $\begingroup$ I clarified $n$ and $m$. I added the assumption that each node has at most $1$ type. $\endgroup$ – Michael Xu Jul 17 '14 at 22:11

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