关于dijkstra算法的困惑？

Question

根据算法书Corman,Dijkstra仅适用于所有边都具有非负权重的图.这是否意味着,如果有任何具有负权重的边缘,它将不适用于整个图形？还是不计算负重量边缘？请说明哪一个是对的？

Answer 1

Dijkstra算法有时可以处理一些负边缘的图形,例如:

A-->B-->C

而w(A, B) = -1和w(B, C) = -2.

但是当至少存在一个负边缘时,它不能证明总是正确的.喜欢:

A-->B-->C-->D
 \         /
  \ _____ /

其中w(A, B) = 1,w(B, C) = 3,w(C, D) = -5,w(A, D) = 2.

如果你选择A作为源点,你将得到从A到D的最短路径的长度是2Dijkstra算法,而不是-1事实.

这是因为Dijkstra算法是一种贪婪算法,其正确性证明程序使用它的所有边缘都是非负的以获得矛盾.关于它的证明程序,你可以在定理24.6(Dijkstra算法的正确性),算法导论中查阅.