Shortest paths candidate
The idea is to build a graph with only the edges that are candidates for the shortest path from $v$ to $u$ assuming that $f$ is the required solution.

If during the process we find an edge that lead to a shorter path then we return false.

Otherwise, at the end, we check that all the nodes are still connected (with a DFS) hence that there exists a path with the required weight.


  if $f(v)\neq 0$ then return false
  
  $\forall e=(v_1,v_2)\in E $ do
  
  if $f(v_2) &gt; f(v_1)+w(e)$ then return false
  
  if $f(v_2) &lt; f(v_1)+w(e)$ then remove $e$ from $E$
  
  done
  
  build $cV$ the set of reachable vertices in the new graph (with a DFS)
  
  return $V=cV$


Correction: 
- if there exists $u\in V$ such that $f(u)&gt;\delta(v,u)$ then there exists $e=(v_1,v_2)\in E$ such that $f(v_2) &gt; f(v_1)+w(e)$. Let $e_1,...,e_n$ be the shortest path from $v$ to $u$ if $f(v_{i+1}) \leq f(v_i)+w(e_i)$ then $f(u)\leq \delta(v,u)$ contradiction.

Hence the algorithm return false.


otherwise if there exists $u\in V$ such that $f(u)&lt;\delta(v,u)$ then $u$ is disconnected from $v$ in the resulting graph.
Hence the algorithm return false. $u$ is connected, hence there exist a path $e_1,...,e_n$ from $v$ to $u$ such that $f(v_{i+1}) = f(v_i)+w(e_i)$ hence $f(u)\geq \delta(v,u)$ contradiction.
otherwise if for all $u\in V$ $f(u)=\delta(v,u)$ then all the edges belonging to the shortest path verify $f(v_{i+1}) = f(v_i)+w(e_i)$ hence are still in the graph at the end hence all the vertices are still connected. Also there are no edges such that $f(v_2) &gt; f(v_1)+w(e)$ otherwise $f(v_2)&gt;\delta(v,v_2)$.


Complexity:

$O(|E|)$ to build the new graph plus $O(|E|)$ for the DFS plus $O(|V|)$ for set equality hence $O(|V|+|E|)$.