1
$\begingroup$

I have the following question: Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every other vertex, i.e $0\leq dist(s,v) < \infty$. Let $f\colon V \to \mathbb R$ a given function. Describe an algorithm that runs in $O(|V| + |E|)$ that determines wethter this given $f$ is the shortest path function from $s$, i.e $\forall v \in V :f(v)=dist(s,v)$.

What I thought about was to check for every $v \in V$ whether $f$ fulfill the two following demands:

  1. $f(s)=0$
  2. $f(v) \leq f(u) + w(uv)$ for all $u \in V$ and $uv \in E$

This runs in the proper complexity. I thought to prove it by showing that $f(v) \leq dist(s,v) \land f(v) \geq dist(u,v) \Rightarrow f(v) = dist(f,v)$

I proved that $f(v) \leq dist(s,v)$, but I am stuck at proving that $f(v) \geq dist(s,v)$.

$\endgroup$
2
$\begingroup$

Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function.

You need to strengthen your second condition.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Forget what I wrote. I need to think about it again. $\endgroup$ – user2207686 Jun 1 at 20:10
  • $\begingroup$ That's unsatisfiable in many cases. $\endgroup$ – Yuval Filmus Jun 1 at 20:11
  • $\begingroup$ OK, I understand what my problem was, I need to change condition 2 to something like: $f(v) = min(f(u) + w(uv)$ for all $u \in V $ and $uv \in E$ Because we need that $f(v)$ to actually be equal to one of the paths and not just lower than all of them. Thank you. I will try to prove it now. $\endgroup$ – user2207686 Jun 2 at 8:14
  • $\begingroup$ Right, that would fix it. $\endgroup$ – Yuval Filmus Jun 2 at 8:15
  • $\begingroup$ I try to prove it, but I still facing the same problem - I can prove that $f(v) \leq dist(s,v)$ ,I only know that $f(v)$ is smaller than something, but I have no clue from what it's bigger than, can I have a clue about how to start it? $\endgroup$ – user2207686 Jun 2 at 10:23

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.