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

Question

Problem Statement:

Let G = (V,E) be a directed graph with costs c_e ∈ ℝ on each edge e ∈ E. There are no negative cycles in G. Suppose there is a sink node t ∈ V, and for each node v ∈ V, there is a label d_v ∈ ℝ.

Give an algorithm that decides, in linear time, whether it is true that for each v ∈ 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) ∈ 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.

Answer 1

Yes, your insight is an ingredient to an efficient algorithm. Given a node u — different from t —, its outgoing edges e=(u,v) should fulfill this condition:

        c_e + v_d ≥ u_d

In addition to this, at least one of those edges e should be in the node's minimum cost path:

        c_e + v_d = u_d

The above two conditions can be condensed into the following, where E_u is the collection of edges that originate in u:

        min(c_e + v_d) = u_d for e=(u,v) ∈ E_u

Finally, the minimum cost path at the sink t should be zero:

        d_t = 0

So, it is possible to design an algorithm that visits all nodes and their outgoing edges exactly once in order to verify these conditions.

Time Complexity

If you have the graph represented with an adjacency list, then this can indeed be done in O(|V| + |E|) time. If the graph is connected, then this boils down to O(|E|).

Pseudo Code

function verify(nodes, sink):
    if sink.label != 0:
        return False
    for node in nodes:
        if node != sink:
            cost = infinity
            for e in node.outgoingEdges:
                cost = min(cost, e.target.label + e.cost) 
            if node.label != cost:
                return False
    return True

For an implementation in Python, see this repl.it