Dijkstra算法处理负权重

Question

Dijkstra算法处理负权重

dijkstra

41

我们能在有负权边的情况下使用 Dijkstra 算法吗？ 注意！ 在你想到“lol nub 你可以无限制地在两个点之间跳跃并获得一条无限便宜的路径”之前，我更多的是考虑单向路径。

一个应用场景是具有山地地形和点的地图。显然从高处到低处不需要耗费能量，事实上，它还能生成能量（因此是一个负权重路径）！但是再次返回就不会那么顺利了，除非你是查克·诺里斯。

我考虑将所有点的权重递增，直到它们非负，但我不确定这是否有效。

- orlp

12

贝尔曼-福德算法是一种用于在加权有向图中寻找单源最短路径的算法。它可以处理负权重边，并且可以检测负权重环路。该算法通过对所有边进行松弛操作来计算从给定源点到所有其他顶点的最短路径。具体来说，它使用迭代的方式，每次迭代都会使路径长度更短，直到找到最短路径为止。如果存在负权重环，则该算法可以侦测到并指出其存在。 - Bart

4

维基百科解释称：与Dijkstra算法不同，只要图中不包含从源节点s可达的负权重环路，Bellman-Ford算法就可以应用于具有负边权的图。（存在这样的循环意味着不存在最短路径，因为每次遍历这个循环时总权重都会变小。） - Rom1

我认为这篇文章：https://dev59.com/q2w15IYBdhLWcg3wJ4YR 是一个更好的解释。 - basarat

如果您预先计算每个节点的最短路径（使用Bellman-Ford算法），从所有入边中减去该路径长度，并将其添加到所有出边中，那么是的。您将得到一个转换后的（现在是有向的）图，其中所有权重都为非负数，可以在其上使用Dijkstra算法。这被称为Johnson算法，它是确定加权图中每对点之间的最短路径的最佳方法，其成本为|V| * O(dijkstras) + O(Bellman) = |V| * O(dijkstras) = |V| * (E + V log V)。 - RussellStewart

这个回答解决了你的问题吗？使用Dijkstra算法处理负权重 - user4157124

显示剩余2条评论

7个回答

3

如果你读过最优性的证明，其中一个假设是所有权重都是非负数。所以，不行。正如Bart建议的那样，如果你的图中没有负环，则使用Bellman-Ford算法。

你必须理解，负边不仅仅是负数——它意味着路径成本的减少。如果你在路径上添加了一条负边，你已经降低了路径的成本——如果你增加权重，使得这条边现在是非负数，它就不再具有这种减少成本的属性，因此这是一个不同的图。

我鼓励你阅读最优性的证明——在那里你将看到添加边到现有路径只能增加（或不影响）路径成本的假设是至关重要的。

- Jacob

那么对于_"我在考虑将所有点的权重递增，直到它们为非负数，但我不确定这是否有效。"_ 有何看法？ - orlp

除非所有路径都穿过相同数量的边，否则这将无法正常工作。否则，您将会相对惩罚那些穿过更多边的路径。 - recursive

@nightcracker - 不会的。考虑这个图：1->2 (cost 10); 1->3 (cost 2); 2->3 (cost -100); 3->4 (cost 2)。你将在每条边上加101，并得到从1到4的最小路径为1->3->4，但是1->2->3->4更好。然而，Dijkstra会错过那个路径，因为节点3只被扩展一次。如果允许它被扩展多次，那么就可以解决问题，但这就不再是Dijkstra算法了，而是变成了Bellman-Ford算法。 - IVlad

你有Dijkstra最初的证明链接吗？可能是荷兰语的吗？他总是用荷兰语写作，我很幸运荷兰语是我的母语。 - orlp

1

@nightcracker 在谷歌上搜索“Dijkstra算法正确性证明”，你会找到它 - 以及关于该算法的很多荷兰文档。 - rlc

2

实际上，有一种算法可以在负路径环境中使用Dijkstra算法。它通过先删除所有的负边并重新平衡图形来实现。这个算法叫做“约翰逊算法”。

它的工作方式是添加一个新节点（假设为Q），该节点对于图中的每个其他节点都具有0的遍历成本。然后从点Q运行Bellman-Ford算法，在相对于Q的每个节点上获取一个成本（我们称之为q [x]），它要么是0，要么是负数（因为它使用了负路径）。

例如，a-> -3-> b，因此如果我们添加一个节点Q，该节点对所有这些节点都具有0成本，则q [a] = 0，q [b] =-3。

然后，我们使用公式：weight + q [source] - q [destination]重新平衡边缘，因此a-> b的新权重为-3 + 0-（-3）= 0。我们对图中的所有其他边执行此操作，然后删除Q及其传出边缘，就完成了！现在我们有一个重新平衡的图形，没有负边缘，我们可以对其运行Dijkstra算法！

运行时间为O（nm）[bellman-ford] + n x O（m log n）[n Dijkstra] + O（n ^ 2）[权重计算] = O（nm log n）时间。

更多信息：http://joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html

- Evil Washing Machine

2

你可以在负权重图上使用Dijkstra算法，但你必须首先为每个节点找到合适的偏移量。这本质上就是Johnson算法所做的事情。但这么做会过度杀伤力，因为Johnson算法使用Bellman-Ford算法来找到权重偏移量。Johnson算法旨在寻找所有节点对之间的最短路径。 http://en.wikipedia.org/wiki/Johnson%27s_algorithm

- Justin

0

实际上，我认为修改边缘权重会起作用。不是使用偏移量，而是使用因子。假设您测量的不是距离，而是从点A到B所需的时间。

权重=时间=距离/速度

您甚至可以根据坡度调整速度，如果您的任务是在真正的山区和汽车/自行车上使用物理速度。

- Karussell

0

是的，您可以通过在最后添加一步来实现这一点，即：

            If v ∈ Q, Then Decrease-Key(Q, v, v.d)
            Else Insert(Q, v) and S = S \ {v}.

- sa_nyc

-5

表达式树是一种二叉树，其中所有叶子节点都是操作数（常量或变量），非叶子节点是二元运算符（+，-，/，*，^）。使用该树来模拟多项式，并实现以下基本方法：

计算多项式的一阶导数的函数。
对于给定的x值，求解多项式的值。

[20] 使用以下规则进行求导：Derivative(constant) = 0 Derivative(x) = 1 Derivative(P(x) + Q(y)) = Derivative(P(x)) + Derivative(Q(y)) Derivative(P(x) - Q(y)) = Derivative(P(x)) - Derivative(Q(y)) Derivative(P(x) * Q(y)) = P(x)*Derivative(Q(y)) + Q(x)*Derivative(P(x)) Derivative(P(x) / Q(y)) = P(x)*Derivative(Q(y)) - Q(x)*Derivative(P(x)) Derivative(P(x) ^ Q(y)) = Q(y) * (P(x) ^(Q(y) - 1)) * Derivative(Q(y))

- zile

我不明白这与我的问题有什么关系，能否解释一下？ - orlp

真的不明白这怎么会与原始的迪杰斯特拉问题有关。 - linello

与 OP 的问题无关。 - A.J.

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

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

- Chiara Coetzee · Accepted Answer

只要图中不包含负权重的有向环（即边权重之和为负数的有向环），它将在任意两点之间拥有最短路径，但Dijkstra算法并不是为了找到它们而设计的。在具有负边权重的有向图中，寻找单源最短路径的最佳算法是Bellman-Ford算法。然而，这也有一个代价：Bellman-Ford需要O(|V|·|E|)时间，而Dijkstra算法需要O(|E| + |V|log|V|)时间，对于稀疏图（其中E为O(|V|)）和密集图（其中E为O(|V|²)）都是渐进更快的。

在您所提到的山地地形的例子中（必须是一个有向图，因为上下坡有不同的权重），不存在负环的可能性，因为这将意味着离开一个点，然后以净能量增益返回该点——这可以用来创建永动机。

增加所有权重的常量值使它们为非负数是行不通的。要理解这一点，请考虑从A到B有两条路径的图形，一条经过长度为2的单条边，另一条经过长度为1、1和-2的边。第二条路径更短，但如果您将所有边权重增加2，则第一条路径现在长度为4，而第二条路径长度为6，反转了最短路径。只有当两个点之间的所有可能路径使用相同数量的边时，此策略才有效。