# Are there algorithms that traverse from two sides of a graph to find an s-t path.

Say I have a directed graph with a source and destination node s and t and I want to see if there's a path that exists between those two nodes.

Intuitively I would think that the fastest way to do this is to traverse forward from s while backtracking from t at the same time. If any nodes collide then you have a path. Most algorithms I see just say to use a breadth first search from s. Wouldn't my "double ended search" be faster?

Does an algorithm like this exist?

Yes, one can do this. This doesn't change the big-Oh of the algorithm, but may speed up by a constant factor. However, that factor depends on the graph. For example, if the graph is a 2-dimensional road system, the number of steps should be porportional to the area covered, which is $2\cdot\pi(\frac r2)^2$ compared to $\pi r^2$, a speedup by $2$. Then again, if the graph is of such geometric nature, one would use A* at least. (Now what about two-sided A*?)