# Verifying the minimum cost from each node to a sink node in linear time

Problem Statement:

Let $$G= (V, E)$$ be a directed graph with costs $$c_e \in \mathbb{R}$$ on each edge $$e \in E$$. There are no negative cycles in $$G$$. Suppose there is a sink node $$t \in V$$, and for each node $$v \in V$$, there is a label $$d_v \in \mathbb{R}$$. Give an algorithm that decides, in linear time, whether it is true that for each $$v \in V$$, $$d_v$$ is the cost of the minimum-cost path from $$v$$ to the sink node $$t$$.

Attempt:

The biggest challenge I find is the linear time limitation. The most relevant algorithm to consider here is the Bellman-Ford algorithm, but runs in $$O(|V|\,|E|)$$ time which is too slow, so it requires modifying for this problem.

I have also made an observation: If, for example, $$(u,v) \in E$$ and $$c_{(u,v)} = 1$$, and $$d_u = 3$$ and $$d_v = 5$$, then the label $$d_v$$ is wrong. This is because passing from $$v$$ to $$u$$ with a cost of $$1$$ and travelling from $$u$$ to $$t$$ in a minimum cost of $$3$$ for a total cost of $$4$$ is shorter than the supposed minimum cost from $$v$$ to $$t$$ given by $$d_v$$, which is $$5$$. I'm not sure if I can use this insight to produce a linear algorithm, but it's the furthest I have gotten so far.

EDIT:

This problem is not a duplicate of the other problem proposed, since the edge weights can be negative in this problem, but the edge weights are positive in the other problem.