Definition Let $D = (V, A)$ be a directed graph, with $r \in V$. Suppose that a directed path from $r$ to $v$ exists, for every $v \in V \setminus {r}$. An r-arborescence in D is by definition a set of arcs $B \subseteq A$ such that $(V, B)$ has a unique directed $r -v$ walk, for every $v \in V \setminus {r}$.
Suppose a length function l : $A \to \mathbb R $ has been given with the graph $D$. We also know that no directed circuits of negative length exist in D. Now, a shortest path tree (SP tree) rooted at $r$ for $(D, l)$ is an r-arborescence $B$ such that the unique $r–v$ path in $(V, B)$ is a shortest path (with respect to l) in D.
Show that a given r-arborescence B is an SP tree if and only if, for every $(u, v) \in A$, $$d_B(r, v) \leq d_B(r, u) + l(u, v)$$ where $d_B(x, y)$ denotes the distance in the graph (V, B) with respect to the length function $l$ restricted to $B \subseteq A$.
My approach: $(\implies)$ We know that if we have an $SP$ tree rooted at $r$, we know that there is a shortest path from $r$ to $v$, because this is a shortest path tree, denote the distance $d_B(r,v)$. If we take any other point $u$ adjacent to $v$ on the shortest path tree we know that the $r-u$ path is also of minimal length. If we are at $u$ we still need to go from $u$ to $v$ now by some arc, this is given by the length function $l(u,v)$, in total we have travelled $d(r,u)+l(u,v)$. We are not certain this way of reaching $v$ will give us a path of minimal distance, but we know lengths are positive, so adding it will give us an inequality:
$$ d_B(r,v) \leq d_B(r,u) + l(u,v)$$ $(\impliedby)$ Now I am not sure how this inequality implies that $B$ is a shortest path tree.
I was thinking of negating the statement and generating some counterexample of the form: Suppose we have a tree that is not a shortest path tree, then there exists an arc $(u,v)$ such that: $$d_B(r,v) > d_B(r,u) +l(u,v) $$
Hint:
distanceandpredecessorarrays calculated from $B$).I hope this helps $\ddot\smile$