1

I'm currently trying to figure out an efficient way to find all nodes on some path between two nodes (say, X and Y) in a directed graph.

My first thought was to run a BFS from X, run a BFS from Y, and take the intersection of visited nodes. Note that I don't need to enumerate all paths between X and Y, just find all nodes that lie on a path from X to Y.

My question is, is there a more optimized way to do this?

kk415kk
  • 1,227
  • 1
  • 14
  • 30

1 Answers1

0

Optimization can be done in terms of getting better run-time or using less memory, or finding a good solution (sometimes a local maximum is ok).

You can look at A* search and see if this can be applied to your problem. You would save both memory and shorten the run-time if you can apply this.

Joelmob
  • 1,076
  • 2
  • 10
  • 22
  • 1
    I'm unsure of how to frame a finding of all nodes on all paths from X to Y into a goal state; I've only used A* in the context of finding the shortest/optimal path to a goal state (i.e. shortest/least cost path from X to Y). – kk415kk Sep 12 '14 at 20:29
  • If I understood you nodes between X and Y would be the same as the nodes that will be traversed on that path. Then this problem would be the same at finding any path between X and Y, is finding the shortest path from X to Y ok? Maybe I didn't understand your question. – Joelmob Sep 13 '14 at 09:34
  • Yup, finding the shortest path can be part of the problem, but I need to find all the nodes on all paths from X to Y. There could be multiple paths of different lengths from X to Y. A* would smartly guide the search to avoid searching some parts of other paths. – kk415kk Sep 13 '14 at 17:04
  • In this case you can forget about the A* search, same question as yours is answered here http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes. Your question said: all nodes on some path. – Joelmob Sep 13 '14 at 17:56
  • Yeah, all nodes on **some** (any) path, not a specific path. Finding all paths is exponential but what I want to know is if there's an optimized way to solve the problem of finding the nodes on a path. My BFS solution is already in linear time - the link you sent me to is going to be exponential to list all paths. – kk415kk Sep 13 '14 at 22:45