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