Given directed connected weighted graph, check if d(v) = delta(s,v) I'm having some hard time with this problem. 
Can someone give me some clue/guidance?

This is an homework question, so please don't just solve it.


  Given a weighted directed connected graph $G = (V,E)$  and given another
  function $d: V \to \mathbb{R}^+$ (including zero), find a linear time algorithm that checks if $d(v)=\text{delta}(s,v)$ for each $v$, for some fixed vertex $s$.
  
  $\text{delta}(s,v)$ is like in Dijkstra algorithm, meaning shortest path from $s$
  to $v$.


My thought is to make use of BST to check if these functions are equal, but I can't avoid running Dijkstra for it.
If $d$ indeed represents the length of the shortest path, we must have 

$$
d(v)=
\begin{cases}
0, &amp;\text{if $v=s$,}\\
\displaystyle\min_{u:(u,v)\in E}\{d(u)+w(u,v)\}, &amp;\text{otherwise,}
\end{cases}
$$

where $w(u,v)$ is the weight of the edge $(u,v)$. 

So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $d$ does not satisfy this property, it cannot represent the length of the shortest path. However, if $d$ does satisfy this property, does it really represent the length of the shortest path? I'll let you figure out this part.

For a further hint:


   Note what you need to prove is that, for all $v$, $d(v)$ is length of the shortest path from $s$ to $v$. Suppose the shortest path from $s$ to $v$ contains $k$ edges, you may try a mathematical induction on $k$.