Given a directed graph $G =(V,E)$, a source Vertex $s \in V$, weight function $w: E \to R^+$ (it is a weighted graph), and a function $d:V \to R^+$. Is there any linear algorithm to check : $\forall v \in V$ if $d(v) = \delta(s,v)$ where $\delta$ is the cost (in weight) from $s$ to $v$.
How can a solution have a linear time $O(V+E)$? The only way I see to solve this problem is to use Dijkstra algorithm (which is not linear of course).
Best Answer
A list of algorithms for shortest path problem for directed graphs with nonnegative weights is provided in the respective section of Wikipedia page.