# Shortest paths candidate

Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. Let $f : V \to \mathbb R$ be a given function. Describe an algorithm that runs in $O(|V| + |E|)$ time that answers yes/no to the question: is it true that for all $u \in V, f(u) = \delta(v,u)$, where $\delta(v,u)$ is the weight of the shortest path from $v$ to $u$?

Obviously what comes to mind is Bellman-Ford algorithm, but it doesn't satisfy the time requirement. I don't really see how having the candidate $f$ function helps us in this regard.

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) > 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 $u\in 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 $u\in 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 $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) > 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|)$.

• What do we do regarding sides with f(v2)<f(v1)+w(e)? – ctlaltdefeat May 19 '13 at 16:06
• Nothing, it's just that $e$ is not part of the shortest path between $v$ and $v_2$ – wece May 19 '13 at 16:23
• Does not work for this graph: $w(s,a) = 10$, $w(s,b) = 10$, $w(a,b)= -1$, $w(b,a)=1$, and $f(s)=0$, $f(a)=4$, $f(b)=3$. – user8446 May 30 '13 at 12:00
• Please remove the incorrect stuff, leaving only a self-contained description of the algorithm you believe is correct. In its current form, this answer is not readable. – JeffE Jun 3 '13 at 1:10
• Assume the first answer never existed, and assume I'm reading this for the first time. I have no idea what "with the same idea as before" means. – Juho Jun 3 '13 at 16:33