0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.