在线性时间内验证从每个节点到汇聚节点的最小成本

Question

问题陈述：

令 G = (V,E) 成为成本为 c_e[=65= 的有向图] ∈ ℝ 在每条边上 e ∈ E。 G中没有负循环。假设有一个sink节点t∈V，对于每个节点v∈V，有一个标签d_v∈ℝ。

给出一个算法，在线性时间内，对于每个 v ∈ V, d_v是从v到sink节点t[的最小代价路径的代价=65=].

尝试：

我发现最大的挑战是线性时间限制。这里考虑的最相关的算法是Bellman-Ford算法，但是运行时间为O(|V|·|E|)太慢，所以需要针对这个问题进行修改。

我也观察了一下：

如果，例如，(u,v) ∈ E 并且 c_(u,v) = 1，并且 d_u = 3和d_v = 5，则标签d_v错了。这是因为从 v 到 u 的成本为 1，从 u 到 t 在最小成本为 3 的情况下总成本为 4 比假定的从 v 到 t[=65 的最小成本要短=] 由 d_v 给出，即 5.

我不确定我是否可以使用这种洞察力来生成线性算法，但这是迄今为止我得到的最远的算法。

Answer 1

是的，您的洞察力是高效算法的重要组成部分。给定一个节点 u——不同于 t——它的出边 e=(u,v)应该满足这个条件：

c_e + v_d ≥ u_d

除此之外，这些边中至少有一条 e 应该在节点的最小成本路径中：

c_e + v_d = u_d

以上两个条件可以浓缩为如下，其中E_u是起源于[=38的边的集合=]u:

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

最后，汇点t的最小成本路径应该为零：

d_t = 0

因此，可以设计一种算法，仅访问所有节点及其出边一次，以验证这些条件。

时间复杂度

如果你有用邻接表表示的图，那么这确实可以在 O(|V| + |E|) 时间内完成。如果图形是连通的，那么这可以归结为 O(|E|).

伪代码

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

有关 Python 中的实现，请参阅 this repl.it

时间复杂度

伪代码

在线性时间内验证从每个节点到汇聚节点的最小成本

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

algorithm

optimization

graph-traversal

graph-algorithm

weighted-graph