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


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.


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.