Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm for path in graph

  1. Dec 24, 2007 #1
    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?

    Last edited: Dec 24, 2007
  2. jcsd
  3. Dec 25, 2007 #2
    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 [tex]A_{ij}[/tex] 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.
    Last edited: Dec 25, 2007
  4. Dec 25, 2007 #3
    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
  5. Dec 26, 2007 #4
    Just go ahead and do a DFS or BFS starting at the beginning of the path then.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook