1

我无法理解为什么 Dijkstra 的算法不适用于具有负边的无环有向图。据我了解，Dijkstra 对图进行了广度优先遍历，并在适当时放松。例如，考虑图表：

S->A (3)
S->B (4)
B->A (-2)

其中 S 是源节点。这就是我想象它的工作方式：

1) 距离为 3 的标记 A。距离为 4 的标记 B。

2) 在 A 上递归。由于 A 不指向任何节点，所以什么也不做。

3）在B上递归。由于B指向A，检查B的距离+B->A是否小于A的当前距离。2 < 3，所以用距离2标记A。

然而，显然这不是它的工作原理，因为我使用的这本书给出了这个图表来说明为什么底片不起作用。我无法遵循书上的解释。Dijkstra 将如何处理这个图表，为什么他们不使用我想象的方法？

4

1 回答 1

4

问题是，一旦你处理了一个节点，你就不能在之后更新它的距离，因为这需要递归更新并且会抛出整个事情（阅读：违背算法的假设，即节点以单调递增的距离处理到来源；请参阅算法的正确性证明以了解需要的地方）。因此，一旦处理了 A，您以后就不能再更改它的距离，这意味着您不能有负边，因为它们可能会使您与先前处理的节点的距离更短。距离单调增加的假设是为什么在处理完节点后将它们标记为黑色，然后忽略黑色节点。因此，即使在该图中 A 到 S 的距离为 2，Dijkstra'

编辑：这是 Dijkstra 算法的作用：

1）用距离3标记A，将其放入等待处理的节点队列中；将距离标记为 4 的 B，将其放入队列中。

2）从队列中取出A，因为它在前面。由于 A 不指向任何节点，因此不要更新任何距离，也不要向队列中添加任何内容。将 A 标记为已处理。

3) 将 B 从队列中取出。B指向A，但是A被标记为已经处理；忽略边 B->A。由于没有更多来自 B 的出边，我们完成了。

编辑 2：关于 D​​AG，您根本不需要 Dijkstra 的算法。有向无环图总是有一个拓扑排序，可以用 O(|V| + |E|) 计算，并按照拓扑顺序处理顶点，使用d(w) = min {d(w); d(v) + c(v, w)}更新距离的规则，其中d(v)是顶点v到源的距离，c(v,w)是边缘的长度(v,w)将为您提供正确的距离，同样在 O(|V| + |E|) 中。总共有两个步骤，每个步骤都需要 O(|V| + |E|)，这就是在具有任意边长的 DAG 中计算单源最短路径的总复杂度。

于 2013-03-27T22:41:18.653 回答