Dijkstra的负权重算法

Question

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

停!在你想到"大笑之后,你可以无休止地在两点之间跳跃并获得一条无限廉价的道路"之前,我更多地考虑单向路径.

申请将是一个山区地形,上面有点.显然,从高到低不会消耗能量,事实上,它会产生能量(因此负路径重量)!但是,除非你是查克诺里斯,否则再回去就行不通.

我想增加所有点的权重,直到它们是非负的,但我不确定这是否会起作用.

Answer 1

只要图形不包含负循环(边缘权重为负值的有向循环),它将在任意两点之间具有最短路径,但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,从而反转最短路径.只有当两点之间的所有可能路径使用相同数量的边时,此策略才有效.