具有负权重的Dijkstra算法 [英] Dijkstra's algorithm with negative weights
问题描述
我们可以使用负权重的Dijkstra算法吗？
停止！在您认为大声笑时，您可以无休止地在两点之间跳转并获得一条无限便宜的路径，我更多地考虑了单向路径。显然，从高变低不会消耗能量，实际上会产生能量（因此负路径权重）！但是除非您是查克·诺里斯（Chuck Norris），否则再回去是行不通的。
我当时想增加所有点的权重，直到它们变为非负数，但是我不确定这是否行得通。
只要图不包含负循环（有向图边缘权重为负的循环），则任意两点之间的路径最短，但Dijkstra的算法并非旨在找到它们。 Bellman是最有名的算法，用于在有向图中以负边缘权重查找有源图的最短路径。 -福特算法。但是，这要付出代价：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，从而反转最短的路径。仅当两点之间的所有可能路径都使用相同数量的边时，此策略才有效。
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.
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.
这篇关于具有负权重的Dijkstra算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
