Is there a true single-pair shortest path algorithm?

Question

I came across this term today "single-pair shortest path problem". I was wondering if a single-pair shortest path algorithm exists for weighted graphs. My reasoning might be flawed, but I imagine that if you want to find the shortest path between A and Z, you absolutely have to know the shortest path from A to B, C, D, ... Y.

If you do not know the latter you can not be sure that your path is in fact the shortest one. Thus for me any shortest path algorithm has to compute the shortest path from A to every other vertex in the graph, in order to get the shortest path from A to Z.

Is this correct?

PS: If yes, any research paper properly proving this?

Answer 1

For non-negative weighted edges graph problem Dijkstra itself solves given problem.

A quote from wiki

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Consider following pseudo code from wiki:

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

with each new iteration of while (12), first step it to pick the vertex u with shortest distance from the remaining set Q (13) and then that vertex is removed from the Q (14) notifying that shortest distance to u has been achieved. If u is your destination then you can halt without considering further edges.

Note that all vertices were used but not all edges and shortest path to all vertices was not yet found.

Answer 2

Quoting CLRS, 3rd Edition, Chapter 24:

Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, all known algorithms for this problem have the same worst-case asymptotic running time as the best single-source algorithms