Dijkstra算法处理源节点有负边的情况

Question

3

当图中存在负权重边时，Dijkstra算法会失败。但是，有一个例外：如果在一个有向无环图中，只有离开源节点的边是负的（其他所有边都是正的），那么我们可以成功地使用Dijkstra算法。

现在我的问题是，在上述例外情况下，如果该图有一个循环会怎样？我相信Dijkstra算法将无法工作，但我无法举出一个具有循环的有向图的例子，且唯一的负边缘是离开源节点这一点对于Dijkstra并不起作用。有人能提供一个例子吗？

- FranXh

1

你为什么认为在这种情况下它会失败？请注意，负边不是任何循环的一部分，因为它们是从源头的出边。 - amit

如果存在一个包含源节点的第一个子节点的循环，那会有问题吗？ - FranXh

我的直觉说不行，但我需要考虑如何证明这一点。 - amit

我一直在努力寻找反例，但一直没有成功... - FranXh

1

相关链接：https://dev59.com/b2025IYBdhLWcg3whWZm - Andrew Tomazos

1

当然，如果存在负权重的循环，则不存在最小权重路径，算法将永远循环。（只是为了明确说明。） - Daniel Fischer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

在您描述的情况下，Dijkstra算法可以很好地工作。但是在带有负权重的一般情况下，它会失败，因为它在每个步骤中贪心地选择要“关闭”的节点，并且关闭的节点永远不会重新打开。

现在假设源点s有k个出边，指向k个不同的节点。让它们的顺序为v1、v2、......、vk（其中v1最小）。请注意，对于每个vi和vj，使得i

因此，在整体上 - 没有造成伤害 - 一旦边缘处于“关闭”状态 - 您将永远不会找到“更短”的路径，因为负边仅来自源。

在这里，我假设您问题中的源代码意味着d_in（source）=0，就像DAG中的“源”一样。如果您的意思是离开源顶点，则可能会有问题，因为看一个两个顶点的图形，使得w（s，t）=-2，w（t，s）=1 - 图形中有一个负循环。因此，为了使上述解释起作用 - 您必须假设d_in（s）=0。