# Determine whether given f is shortest path function

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

Your conditions are not enough. For example, the function $$f(v) \equiv 0$$ satisfies them, but is (usually) not the shortest distance function.
• 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. Jun 2 '20 at 8:14
• 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? Jun 2 '20 at 10:23