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:

- $ f(s)=0$
- $ 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)$ .