Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Question

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$.

If both source $s$ and destination $t$ are fixed, can we compute the shortest path from $s$ to $t$ without computing distances for all other nodes from $s$?

More fundamentally,

Is single-source single-destination shortest path problem easier (e.g., in terms of worst-case time complexity) than its single-source all-destination counterpart?

Answer 1

Nope. In order to find the distance from $s$ to $t$ it is necessary to determine the length of all paths that are at least at the same distance as $t$ is. If $t$ has a "median" distance half of the distances will be known that way.

In certain application areas (with an exponentially sized "implicit" state space) it can still be worthwhile to start searching from both sides and look for nodes that are found in the middle.

Answer 2

I found some comments on the problem in this video lecture on Algorithms (by MIT; from 17min:45sec $\sim$ 18min:30sec), as transcribed as follows:

It turns out, this is one of the wired things about shortest paths, according to the-state of-the-art we know today, it seems to be the best algorithm for solving the $A$ to $B$ problem (given $s$, given $t$, go from $s$ to $t$) is no easier than this problem (going from $s$ to all vertices).

The best way we know how to solve going from $A$ to $B$ is to solve how to go from $A$ to everywhere else.

Therefore, it seems to be still a hard research-level problem.