sandesh247/problems — Issue #1: Verify minimum cost path for directed graph
Author: sandesh247
Created: 2011-10-19 05:34:06+00:00
State: open
Labels: algorithm, dynamic programming, flow, n, n log n

Suppose you are given a directed graph G = (V, E) with costs on the edges ce for e ∈ E and a sink t (costs may be negative). Assume that you also have ﬁnite values d(v) for v ∈ V . Someone claims that, for each node v ∈ V , the quantity d(v) is the cost of the minimum-cost path from node v to the sink t.

(a) Give a linear-time algorithm (time O(m) if the graph has m edges) that veriﬁes whether this claim is correct.

(b) Assume that a distance are correct, and d(v) is ﬁnite for all v ∈ V . Now you need to compute distances to a diﬀerent sink t′. Give an O(m log m) algorithm for computing distance d′(v) for all nodes v ∈ V to the sink node t′.