Given a directed acyclic (and unweighted) graph and two distinct vertices S and T, is there an algorithm that will tell me if there is any path (not necessarily the shortest one) between the two? If it helps, I don't need the list of vertices on this path, just the fact that path exists.

I sure know of all the graph shortest-path algorithms (Dijsktra/Bellman-Ford/topological sorting/etc.), but I don't actually need the shortest one. Is there a speedy method of finding any arbitrary path in a DAG between two nodes? Pretty sure there is aplenty of specialized algorithms for that, just not sure where to search for.

  • 2
    $\begingroup$ Use BFS or DFS. $\endgroup$ – Yuval Filmus Mar 23 '18 at 8:00

Think of it that way: If given a DAG and two vertices $s,t$ (with no other information) you can't get any better than linear time.

Once you understand that, asymptotically you won't get any better than algorithms such as BFS or DFS. So in your case, solving a "harder" problem (i.e finding the shortest path) is the same (complexity-wise) as solving your problem (finding any path). Therefore BFS or DFS will be the exactly algorithms you search for.

  • $\begingroup$ Thank you, this is sort of the answer I was searching for :) $\endgroup$ – Dmitriy Khudorozhkov Mar 23 '18 at 16:40

Literally any search algorithm will do this; the simplest are probably breadth-first- and depth-first search.


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.