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