Problem Detail: 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?
Asked By : hengxin
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33136
