2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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|)$.

$\endgroup$
  • $\begingroup$ What do we do regarding sides with f(v2)<f(v1)+w(e)? $\endgroup$ – ctlaltdefeat May 19 '13 at 16:06
  • $\begingroup$ Nothing, it's just that $e$ is not part of the shortest path between $v$ and $v_2$ $\endgroup$ – wece May 19 '13 at 16:23
  • $\begingroup$ 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$. $\endgroup$ – user8446 May 30 '13 at 12:00
  • 3
    $\begingroup$ 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. $\endgroup$ – JeffE Jun 3 '13 at 1:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Juho Jun 3 '13 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.