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?
On
This is relatively common in robotics, where the set of nodes of the graph are practically infinite, and we need to sample some of them. For example, see the paper on the expansive search tree (Path planning in expansive configuration spaces by D. Hsu). As Hagen von Eitzen point out, however, in the worst case this heuristic do not reduce the worst case complexity. However in most cases (or at least in robotics), the number of nodes expanded increase proportionally to the distance from the origin node in the search graph, so this technique usually decrease the number of expanded nodes by a noticeable constant.
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*?)