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.
