Now I know that there is a distinction between single source shortest path algorithms and all-pair shortest path algorithm . My question is the following:
If we solve the single source (let's say s ) shortest path problem , we have also solved it for some pairs that do not contain s , haven't we ? And to be exact we have solve it for every pair $q, r$ such that $q, r \in p $ where p is the shortest path between $s$ and another vertex $m$ . To put it mathematically :
$$ d(s, t) = d(s, v) + d(v, t) \;, \forall v \in p$$ where p is the path of length $d(s, v)$
Proof: If there exists a shorter path $s, v$ of length $x(s, v) $ then by following it we get $x(s, v) + d(v, t) < d(s, t)$ an even shorter path from the shortest (which is self contradicting ) . Similarly we can verify that $d(v, t)$ must be the shortest path between $v, t$.
So by this property we can split a shortest path $s, t$ into a sum and get the shortest path between some pairs that do not contain $s$ (for example between $v, t$ in the example above
Is my proof correct? Does this property hold?