具有负权重的 Dijkstra 算法
我们可以使用具有负权重的 Dijkstra 算法吗？
停止！ 在你想到“哈哈，你可以在两点之间无休止地跳跃并获得一条无限便宜的路径”之前，我更想的是单向路径。
其应用是具有点的山区地形。显然，从高到低并不需要能量，事实上，它会产生能量（因此是负路径权重）！但再回去就不行了，除非你是查克·诺里斯。
我正在考虑增加所有点的权重，直到它们为非负数，但我不确定这是否有效。
Can we use Dijkstra's algorithm with negative weights?
STOP! Before you think "lol nub you can just endlessly hop between two points and get an infinitely cheap path", I'm more thinking of one-way paths.
An application for this would be a mountainous terrain with points on it. Obviously going from high to low doesn't take energy, in fact, it generates energy (thus a negative path weight)! But going back again just wouldn't work that way, unless you are Chuck Norris.
I was thinking of incrementing the weight of all points until they are non-negative, but I'm not sure whether that will work.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
只要图不包含负环（边权重和为负的有向环），任意两点之间就会有一条最短路径，但 Dijkstra 算法并不是为了找到它们而设计的。在具有负边权重的有向图中查找单源最短路径的最著名算法是 Bellman -福特算法。然而，这是有代价的：贝尔曼-福特需要 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，从而反转最短路径。仅当两点之间的所有可能路径都使用相同数量的边时，此策略才有效。
As long as the graph does not contain a negative cycle (a directed cycle whose edge weights have a negative sum), it will have a shortest path between any two points, but Dijkstra's algorithm is not designed to find them. The best-known algorithm for finding single-source shortest paths in a directed graph with negative edge weights is the Bellman-Ford algorithm. This comes at a cost, however: Bellman-Ford requires O(|V|·|E|) time, while Dijkstra's requires O(|E| + |V|log|V|) time, which is asymptotically faster for both sparse graphs (where E is O(|V|)) and dense graphs (where E is O(|V|^2)).
In your example of a mountainous terrain (necessarily a directed graph, since going up and down an incline have different weights) there is no possibility of a negative cycle, since this would imply leaving a point and then returning to it with a net energy gain - which could be used to create a perpetual motion machine.
Increasing all the weights by a constant value so that they are non-negative will not work. To see this, consider the graph where there are two paths from A to B, one traversing a single edge of length 2, and one traversing edges of length 1, 1, and -2. The second path is shorter, but if you increase all edge weights by 2, the first path now has length 4, and the second path has length 6, reversing the shortest paths. This tactic will only work if all possible paths between the two points use the same number of edges.
如果您阅读了最优性证明，就会发现其中的假设之一是所有权重都是非负的。所以，不。正如巴特建议的那样，如果图表中没有负循环，请使用贝尔曼-福特。
您必须明白，负边沿不仅仅是一个负数——它意味着路径成本的减少。如果您向路径添加负边，则减少了路径的成本——如果您增加权重以使该边现在非负，则它不具有减少属性不再如此，因此这是一个不同的图表。
我鼓励您阅读最优性证明——在那里您将看到，向现有路径添加边缘只能增加（或不影响）路径成本的假设至关重要。
If you read the proof of optimality, one of the assumptions made is that all the weights are non-negative. So, no. As Bart recommends, use Bellman-Ford if there are no negative cycles in your graph.
You have to understand that a negative edge isn't just a negative number --- it implies a reduction in the cost of the path. If you add a negative edge to your path, you have reduced the cost of the path --- if you increment the weights so that this edge is now non-negative, it does not have that reducing property anymore and thus this is a different graph.
I encourage you to read the proof of optimality --- there you will see that the assumption that adding an edge to an existing path can only increase (or not affect) the cost of the path is critical.
您可以在负加权图上使用 Dijkstra，但首先必须找到每个顶点的正确偏移量。这本质上就是约翰逊算法的作用。但这就太过分了，因为约翰逊使用贝尔曼-福特来找到重量补偿。 Johnson 设计用于顶点对之间的所有最短路径。
http://en.wikipedia.org/wiki/Johnson%27s_algorithm
You can use Dijkstra's on a negative weighted graph but you first have to find the proper offset for each Vertex. That is essentially what Johnson's algorithm does. But that would be overkill since Johnson's uses Bellman-Ford to find the weight offset(s). Johnson's is designed to all shortest paths between pairs of Vertices.
http://en.wikipedia.org/wiki/Johnson%27s_algorithm
实际上有一种算法是在负路径环境下使用Dijkstra算法；它通过首先删除所有负边并重新平衡图形来实现这一点。该算法称为“约翰逊算法”。
它的工作方式是添加一个新节点（假设为 Q），该节点遍历图中每个其他节点的成本为 0。然后，它从 Q 点开始在图上运行 Bellman-Ford，获取每个节点相对于 Q 的成本，我们将其称为 q[x]，该成本要么是 0 要么是负数（因为它使用了负路径之一） ）。
例如a-> -3-> b，因此，如果我们向所有这些节点添加一个成本为 0 的节点 Q，则 q[a] = 0，q[b] = -3。
然后，我们使用公式重新平衡边：权重 + q[源] - q[目的地]，因此 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/约翰逊算法.html
There is actually an algorithm which uses Dijkstra's algorithm in a negative path environment; it does so by removing all the negative edges and rebalancing the graph first. This algorithm is called 'Johnson's Algorithm'.
The way it works is by adding a new node (lets say Q) which has 0 cost to traverse to every other node in the graph. It then runs Bellman-Ford on the graph from point Q, getting a cost for each node with respect to Q which we will call q[x], which will either be 0 or a negative number (as it used one of the negative paths).
E.g. a -> -3 -> b, therefore if we add a node Q which has 0 cost to all of these nodes, then q[a] = 0, q[b] = -3.
We then rebalance out the edges using the formula: weight + q[source] - q[destination], so the new weight of a->b is -3 + 0 - (-3) = 0. We do this for all other edges in the graph, then remove Q and its outgoing edges and voila! We now have a rebalanced graph with no negative edges to which we can run dijkstra's on!
The running time is O(nm) [bellman-ford] + n x O(m log n) [n Dijkstra's] + O(n^2) [weight computation] = O (nm log n) time
More info: http://joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html
实际上我认为修改边缘权重会起作用。不是有偏移量，而是有一个系数。假设您不是测量距离，而是测量从 A 点到 B 点所需的时间。
重量 = 时间 = 距离 / 速度
如果您的任务是针对真正的山脉和汽车/自行车，您甚至可以根据坡度调整速度以使用物理速度。
Actually I think it'll work to modify the edge weights. Not with an offset but with a factor. Assume instead of measuring the distance you are measuring the time required from point A to B.
weight = time = distance / velocity
You could even adapt velocity depending on the slope to use the physical one if your task is for real mountains and car/bike.
是的，您可以通过在最后添加一个步骤来做到这一点，即
Yes, you could do that with adding one step at the end i.e.