0

问题陈述：

令G = (V,E)是一个有向图，在每条边e ∈ E上具有成本c e ∈ ℝ 。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，比d v给出的从v到t的假设最低成本（5 .

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

4

1 回答 1

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 中的实现，请参阅此 repl.it

于 2019-09-10T08:29:05.927 回答