3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure what this adds over Hendrik's answer. This quote just makes a claim without explaining why -- whereas Hendrik's answer explains the intuition why. $\endgroup$ – D.W. Nov 16 '14 at 8:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.