1
$\begingroup$

In my world there are nodes and lines, I want to see if there is any path between node A, and node B, that do not cross any line(including the lines of the path itself) and do not go thru the same node twice. What would be the efficiency of such algorithm and where can I find more information about it.

So far I been reading about A* algorithm, but I do not need the shortest path, just to see if there is any path like this exist at all.

$\endgroup$
  • 1
    $\begingroup$ I think you need to give us more information about the problem, and maybe draw an example. Why can't you build a graph, where the vertices are nodes, and there's an edge between node A and node B if you can get from node A to node B (without crossing any line)? Then you should be able to compute reachability in this graph using any standard algorithm (e.g., depth-first search). $\endgroup$ – D.W. Oct 20 '13 at 6:31
  • 1
    $\begingroup$ A* is a general algorithm, and it also needs a heuristic function. In particular cases you may be able to do with other algorithms - it all depends on the setting. I join D.W. in his query to not leave us in the dark. $\endgroup$ – Yuval Filmus Oct 20 '13 at 6:36
  • $\begingroup$ Babibu, is the following question looking for the same thing you are looking for? cs.stackexchange.com/q/16269/755 Is that the same question, or is it different? (That one is stated more precisely, so it'd be a great model to copy from.) $\endgroup$ – D.W. Oct 21 '13 at 1:02
2
$\begingroup$

Depth-first search or Breadth-first search. Note that Dijkstra's algorithm, essentially reduces to breadth-first-search with equal-cost-paths.

You can also do a sort of meet-in-the-middle (known as a bidirectional search), starting a search from both ends.

Any algorithm for detecting connected-components will work here as well (again, these essentially using one of the search algorithms and adding connected nodes to some collection). However, you can perhaps use the some sort of disjoint-set-data-structure to keep track of different components as you add "lines" into the graph, and thus quickly test if the component of $A$ is the same as $B$. See also: connected-component labeling, and partition refinement.

If your nodes have a special structure, you might be able to take advantage of it. For example, if you are thinking of nodes in euclidean space, you can use a spatial-index, such as a quad-tree, to speed the traversal/search by traversing whole globs of nodes in one shot when it is far from a line/obstacle. Another example would be to use A*, even if you don't care about shortest-path, it might be better than simple breadth-first/depth-first, because of the structure and heuristic you can provide (see best-first search and beam-search).

EDIT:

I thought of another formulation of the problem (which likely would use one or a combination of the above approaches): Is there an online-algorithm to keep track of components in a changing undirected graph:

$\endgroup$
  • $\begingroup$ Aren't the worse case of all those is O(N!) $\endgroup$ – Ilya Gazman Oct 20 '13 at 8:41
  • $\begingroup$ @Babibu no, time complexity of BFS is $\mathcal{O}\left(|V|+|E|\right)$. $\endgroup$ – Realz Slaw Oct 20 '13 at 10:33
  • 1
    $\begingroup$ @G.Bach I assume he has a graph that has some edges which he doesn't want to cross ("lines"? or "lines" cross these edges?), and he wants to know if a path exists between A and B. So I simply say, remove those invalid edges from the graph, and do BFS or DFS. Not crossing the path itself is automatic, as shortest path takes care of that, and this is similar. $\endgroup$ – Realz Slaw Oct 20 '13 at 10:48
  • 2
    $\begingroup$ @Babibu What do you mean by "intersection" in this question. What are "lines"? $\endgroup$ – G. Bach Oct 20 '13 at 10:52
  • 1
    $\begingroup$ @Babibu I thought you had a graph? The connection between two nodes is usually called an edge. A concept of "crossing" edges is not defined on graphs in general. Is your graph embedded? $\endgroup$ – G. Bach Oct 20 '13 at 11:06

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.