Dijkstra的负权重算法
我们可以使用Dijkstra算法的负权重吗？
停！ 在你想到“大声笑，你可以无止境地在两点之间跳跃并获得无限便宜的路径”之前，我更多地考虑单向路径。
一个应用程序将是一个山峰上的地形。 显然，从高到低并不需要能量，事实上，它会产生能量（因此会产生消极的重量）！ 但是如果你不是Chuck Norris，那么再回去就不会那么奏效。
我正在考虑增加所有积分的重量，直到它们是非负数，但我不确定这是否会起作用。
只要图中不包含负循环（边的权重总和为负的有向循环），它将在任意两点之间有一条最短路径，但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，从而反转最短路径。 这种策略只有在两点之间的所有可能路径使用相同数量的边缘时才有效。
如果你阅读最优性的证明，其中一个假设是所有的权重都是非负的。 所以， 不 。 按照Bart的建议，如果图表中没有负循环，则使用Bellman-Ford。
你必须明白，消极的边缘不仅仅是一个负数 - 它意味着降低路径的成本。 如果为路径添加负边缘，则可以降低路径成本---如果增加权重以使此边缘现在不是负面的，则它不再具有减少的属性，因此这是不同的图形。
我鼓励你阅读最优性的证明---在那里你会看到，增加边缘到现有路径的假设只能增加（或不影响）路径的成本是至关重要的。
您可以在负权重图上使用Dijkstra's，但首先必须为每个顶点找到适当的偏移量。 这基本上是约翰逊的算法所做的。 但是，自从约翰逊使用贝尔曼 - 福特找到重量偏移量以来，这将会过度。 约翰逊的设计适用于顶点对之间的所有最短路径。
http://en.wikipedia.org/wiki/Johnson%27s_algorithm
链接地址: http://www.djcxy.com/p/35239.html上一篇: Dijkstra's algorithm with negative weights
下一篇: Dijkstra's algorithm with negative edges on a directed graph