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

Question

问题陈述：

令 G = (V,E) 为有向图，每条边 e _∈ E 上的成本为 ce ∈ ℝ。 G 中不存在负循环。假设有一个汇节点 t ∈ V，并且对于每个节点 v ∈ V，都有一个标签 d_v ∈ ℝ。

给出一个算法，在线性时间内决定对于每个 v ∈ V，d_v 是否是从 v 到汇聚节点的最小成本路径的成本 t.

尝试：

我发现最大的挑战是线性时间限制。这里要考虑的最相关的算法是 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 假设的最小成本要短到 dv _给出的 t，即 5。

我不确定是否可以利用这种见解来生成线性算法，但这是迄今为止我所取得的最远的成果。

Answer 1

是的，您的洞察力是高效算法的一个要素。给定一个节点 u（与 t 不同），其出边 e=(u,v) 应满足以下条件：

        c_e + v_d ≥ u_d

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

        c_e + v_d = u_d

上述两个条件可以简化为以下形式，其中E_u是源自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

Answer 2

检查的答案似乎不正确。假设该图有 4 个节点 A、B、C、D，边为 (A, B)、(B,C)、(C,A)、(B,D)、(C,D)，权重为 0、0，分别为 0、1、1。水槽是D。

如果所有节点的标签均为 0，则上述算法将返回 true，这显然是不正确的。