41

我们可以使用带有负权重的 Dijkstra 算法吗？

停止！在你认为“大声笑你可以在两点之间无休止地跳跃并获得一条无限便宜的路径”之前，我更多地考虑的是单向路径。

一个应用程序将是一个多山的地形，上面有点。显然从高到低并不消耗能量，事实上，它会产生能量（因此是负路径权重）！但是再回去是行不通的，除非你是查克·诺里斯。

我正在考虑增加所有点的权重，直到它们变为非负数，但我不确定这是否可行。

4

7 回答 7

71

只要图不包含负环（边权重为负和的有向环），它将在任意两点之间有最短路径，但 Dijkstra 的算法并非旨在找到它们。在具有负边权重的有向图中寻找单源最短路径的最著名算法是Bellman-Ford 算法。然而，这是有代价的：Bellman-Ford 需要 O(|V|·|E|) 时间，而Dijkstra需要 O(|E| + |V|log|V|) 时间，这对于两个稀疏算法来说都渐近更快图（其中 E 为 O(|V|)）和密集图（其中 E 为 O(|V|^2)）。

在您的山区示例中（必须是有向图，因为上下斜坡具有不同的权重）不可能出现负循环，因为这意味着离开一个点，然后以净能量增益返回该点- 可以用来制造永动机。

将所有权重增加一个常数值以使其为非负数将不起作用。要了解这一点，请考虑从 A 到 B 有两条路径的图，一条穿过长度为 2 的单条边，一条穿过长度为 1、1 和 -2 的边。第二条路径较短，但如果将所有边权重增加 2，则第一条路径的长度现在为 4，第二条路径的长度为 6，将最短路径颠倒过来。这种策略只有在两点之间的所有可能路径都使用相同数量的边时才有效。

于 2011-05-10T21:24:04.600 回答
3

如果您阅读最优性证明，其中一个假设是所有权重都是非负的。所以，不。正如 Bart 建议的那样，如果您的图表中没有负循环，请使用 Bellman-Ford。

您必须了解，负边缘不仅仅是一个负数——它意味着路径成本的降低。如果向路径添加负边，则降低了路径的成本 --- 如果增加权重以使该边现在为非负，则它不再具有该减少属性，因此这是不同的图形。

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

于 2011-05-10T21:21:08.403 回答
2

实际上有一种算法在负路径环境中使用 Dijkstra 算法；它通过删除所有负边并首先重新平衡图形来做到这一点。该算法称为“约翰逊算法”。

它的工作方式是添加一个新节点（比如说 Q），该节点遍历图中所有其他节点的成本为 0。然后它从点 Q 在图上运行 Bellman-Ford，得到每个节点相对于 Q 的成本，我们将其称为 q[x]，它可以是 0 或负数（因为它使用了负路径之一）。

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

然后我们使用公式重新平衡边缘：weight + q[source] - q[destination]，所以 a->b 的新权重是 -3 + 0 - (-3) = 0。我们对所有其他的图中的边，然后删除 Q 及其传出边，瞧！我们现在有一个没有负边的重新平衡图，我们可以在上面运行 dijkstra！

运行时间为 O(nm) [bellman-ford] + nx O(m log n) [n Dijkstra's] + O(n^2) [权重计算] = O (nm log n) 时间

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

于 2013-05-16T23:41:33.070 回答
2

您可以在负加权图上使用 Dijkstra，但您首先必须为每个顶点找到适当的偏移量。这基本上就是约翰逊的算法所做的。但这将是矫枉过正，因为约翰逊使用贝尔曼福特来找到重量偏移量。Johnson's 设计用于顶点对之间的所有最短路径。

http://en.wikipedia.org/wiki/Johnson%27s_algorithm

于 2012-01-17T04:10:31.330 回答
0

是的，你可以通过在最后添加一个步骤来做到这一点，即

            If v ∈ Q, Then Decrease-Key(Q, v, v.d)
            Else Insert(Q, v) and S = S \ {v}.
于 2012-12-09T01:14:49.563 回答
0

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

重量=时间=距离/速度

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

于 2012-10-10T11:31:54.817 回答
-4

表达式树是一棵二叉树，其中所有叶子都是操作数（常量或变量），非叶子节点是二元运算符（+, -, /, *, ^）。使用树的基本方法实现此树以对多项式进行建模，包括以下内容：

  1. 计算多项式的一阶导数的函数。
  2. 计算给定 x 值的多项式。

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

于 2012-12-14T06:21:35.587 回答