理解为什么 Dijkstra 算法在具有负边的图上失败的解释？
Understanding this explanation on why Dijkstra's algorithm fails on graphs with negative edges?
我正在阅读 Sanjoy DasGupta 的书名算法（第 122 页）中有关存在负边的最短路径的内容
http://beust.com/algorithms.pdf
Dijkstra's algorithm works in part because the shortest path from the
starting point s to any node v must pass exclusively through nodes
that are closer than v. This no longer holds when edge lengths can be
negative. In Figure 4.12, the shortest path from S to A passes through
B,a node that is further away.
(S,A) = 3, (S,B)=4, (B,A)= =2
S-----3--------A
| ^
| |
4 -2
| |
| |
B----------->
What needs to be changed in order to accommodate this new
complication? To answer this, let's take a particular high-level view
of Dijkstra's algorithm. A crucial invariant is that the dist values
it maintains are always either overestimates or exactly correct. They
start off at infinity, and the only way they ever change is by
updating along an edge
:
procedure update((u; v) belongsto E)
dist(v) = min{dist(v), dist(u) + l(u,v)}
This update operation is simply an expression of the fact that the
distance to v cannot possibly be more than the distance to u, plus
l(u, v). It has the following properties.
1. It gives the correct distance to v in the particular case where u is the second-last node in the shortest path to v, and dist(u) is
correctly set.
2. It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt.
This operation is extremely useful: it is harmless, and if used
carefully, will correctly set distances. In fact, Dijkstra's algorithm
can be thought of simply as a sequence of update's. We know this
particular sequence doesn't work with negative edges, but is there
some other sequence that does? To get a sense of the properties this
sequence must possess, let's pick a node t and look at the shortest
path to it from s.
我对以上文字的问题是
- 作者所说的秒 属性 是什么意思？ "It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt."我无法理解这个
- 作者的意思是什么"We know this particular sequence doesn't work with negative edges, but is there some other sequence that does?"我不是以英语为母语的人所以很难理解这句话？
关于您的第一个问题 - "it will never make dist(v) too small" 语句是什么意思？ - 我认为作者指的是 Dijkstra 算法的特定 属性：如果您查看 Dijkstra 算法存储到图中每个节点的距离，存储到特定节点的距离永远不会小于实际距离.事实上，如果您具有非负边权重并按照 运行 Dijkstra 算法查看距离，则距离将不断减小，直到它们最终收敛于真实距离。从这个意义上说，Dijkstra 的算法不断地获得越来越好的真实距离近似值，但在任何时候到节点的距离都不会太短。
关于你的第二个问题，我认为作者是要你思考如果你在任何输入图上使用 运行 Dijkstra 算法会发生什么。作为算法 运行s，它不断更新其对图中起始节点与每个其他节点之间距离的猜测。作者是说，如果您 运行 Dijkstra 的算法并观察它是如何工作的，您将看到对某些子例程 update 的一系列调用会改变这些距离。即使算法给出了错误的最终答案，它仍然通过重复调用 update 来工作。
我正在阅读 Sanjoy DasGupta 的书名算法（第 122 页）中有关存在负边的最短路径的内容
http://beust.com/algorithms.pdf
Dijkstra's algorithm works in part because the shortest path from the starting point s to any node v must pass exclusively through nodes that are closer than v. This no longer holds when edge lengths can be negative. In Figure 4.12, the shortest path from S to A passes through B,a node that is further away.
(S,A) = 3, (S,B)=4, (B,A)= =2
S-----3--------A
| ^
| |
4 -2
| |
| |
B----------->
What needs to be changed in order to accommodate this new complication? To answer this, let's take a particular high-level view of Dijkstra's algorithm. A crucial invariant is that the dist values it maintains are always either overestimates or exactly correct. They start off at infinity, and the only way they ever change is by updating along an edge
:
procedure update((u; v) belongsto E)
dist(v) = min{dist(v), dist(u) + l(u,v)}
This update operation is simply an expression of the fact that the distance to v cannot possibly be more than the distance to u, plus l(u, v). It has the following properties. 1. It gives the correct distance to v in the particular case where u is the second-last node in the shortest path to v, and dist(u) is correctly set. 2. It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt.
This operation is extremely useful: it is harmless, and if used carefully, will correctly set distances. In fact, Dijkstra's algorithm can be thought of simply as a sequence of update's. We know this particular sequence doesn't work with negative edges, but is there some other sequence that does? To get a sense of the properties this sequence must possess, let's pick a node t and look at the shortest path to it from s.
我对以上文字的问题是
- 作者所说的秒 属性 是什么意思？ "It will never make dist(v) too small, and in this sense it is safe. For instance, a slew of extraneous update's can't hurt."我无法理解这个
- 作者的意思是什么"We know this particular sequence doesn't work with negative edges, but is there some other sequence that does?"我不是以英语为母语的人所以很难理解这句话？
关于您的第一个问题 - "it will never make dist(v) too small" 语句是什么意思？ - 我认为作者指的是 Dijkstra 算法的特定 属性：如果您查看 Dijkstra 算法存储到图中每个节点的距离，存储到特定节点的距离永远不会小于实际距离.事实上，如果您具有非负边权重并按照 运行 Dijkstra 算法查看距离，则距离将不断减小，直到它们最终收敛于真实距离。从这个意义上说，Dijkstra 的算法不断地获得越来越好的真实距离近似值，但在任何时候到节点的距离都不会太短。
关于你的第二个问题，我认为作者是要你思考如果你在任何输入图上使用 运行 Dijkstra 算法会发生什么。作为算法 运行s，它不断更新其对图中起始节点与每个其他节点之间距离的猜测。作者是说，如果您 运行 Dijkstra 的算法并观察它是如何工作的，您将看到对某些子例程 update 的一系列调用会改变这些距离。即使算法给出了错误的最终答案，它仍然通过重复调用 update 来工作。