Fast Algorithm for Determining Path Existence in a Graph?

[sid_galt]

Is there an algorithm which is O(1) or O(log n) (basically a very fast algorithm) which can tell whether there is a path from a node A to a node B in a graph?

Thanks

 

[Coin]

Do you have to find a path? Or do you just want to know whether a path exists?

If you want to find a path, I suggest looking at the algorithms listed on the wiki for "shortest path problem". In particular dijkstra [sp]'s algorithm is like O(n log n) if you implement it smartly.

If you just want to know whether one exists... in that case you can just do a normal Depth-First Search or Breadth-First Search, both of which are like O(n).

If you have one graph and you will be performing lots of queries on it there is one trick where, as described here, if you convert the graph to an adjacency matrix, and then take that matrix to the power of N, then the resulting matrix A_{ij} will tell you whether a path of length N exists between i and j. So if you just take the initial adjacency matrix to the powers 1 through [longest path], and save the results as you go to another matrix, then you'll have a nice little cache that you can do O(1) queries from. (I actually don't know if this is the best way to create such a cache, it's just the only thing I can think of off the top of my head! Actually I think matrix multiplication costs O(n^3) or something, so it seems certain that a more direct method could do the same thing much faster.)

EDIT: Also, note that the "shortest path algorithm"s listed are for weighted graphs. For an unweighted graph, a breadth-first search will actually find an optimal path and you won't even have any need for a fancy algorithm ilke dijikstra [sp]'s.

 

[sid_galt]

Thanks for the reply. I just need a true and false answer as to whether a path exists or not.
Unfortunately the adjacency matrix trick won't work because the adjacency matrix itself is
n^2 big (n being the number of nodes in the graph) making the whole operation atleast
O(n^2).

 

[Coin]

Just go ahead and do a DFS or BFS starting at the beginning of the path then.