[Solved]: Shortest paths candidate

if $f(v)neq 0$ then return false $forall e=(v_1,v_2)in E $ do if $f(v_2) > f(v_1)+w(e)$ then return false if $f(v_2) < 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 $uin V$ such that $f(u)>delta(v,u)$ then there exists $e=(v_1,v_2)in E$ such that $f(v_2) > 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 $uin V$ such that $f(u)<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 $uin 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) > f(v_1)+w(e)$ otherwise $f(v_2)>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|)$.