为什么 Dijkstra 的算法不适用于负权重边?

问题描述

有人能告诉我为什么 Dijkstra 的单源最短路径算法假设边必须是非负的.

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative.

我说的只是边缘而不是负权重循环.

I am talking about only edges not the negative weight cycles.

推荐答案

回忆一下在 Dijkstra 的算法中，一旦一个顶点被标记为封闭的"(并且在开集之外)——算法找到了最短路径，并且永远不必再次开发此节点 - 它假定开发到此路径的路径最短.

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

但是对于负权重 - 这可能不是真的.例如:

But with negative weights - it might not be true. For example:

       A
      /
     /
    /
   5       2
  /
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

来自 A 的 Dijkstra 将首先开发 C，然后将无法找到 A->B->C

Dijkstra from A will first develop C, and will later fail to find A->B->C

编辑更深入的解释:

请注意，这很重要，因为在每个松弛步骤中，算法假定关闭"节点的成本"确实最小，因此接下来将被选择的节点也是最小的.

Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

它的想法是:如果我们有一个开放的顶点，它的成本是最小的——通过向任何顶点添加任何正数——最小性永远不会改变.
如果没有对正数的约束 - 上述假设不成立.

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

由于我们确实知道"每个关闭"的顶点是最小的 - 我们可以安全地进行松弛步骤 - 无需回头看".如果我们确实需要回头看" - Bellman-Ford 提供了类似递归(DP) 这样做的解决方案.

Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.

这篇关于为什么 Dijkstra 的算法不适用于负权重边?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！