舉個反例好了
B
A D
C
G為無向圖 包含點ABCD 邊AB BD CD AC
w(AB) = 100000
w(AC) = -10
w(CD) = 1000000000000
w(BD) = -10000000
求A->D 的最短路徑
------------
依照演算法運作方式
他會先選擇AC可是這樣他就只能走CD這個莫名大的路徑
錯失了 AB BD 這個比較好的路徑
------------
因為他是建立再選當前最好的路徑
而且又是不可逆的！
又稱 Label Setting Algorithm
所以你用負的權重去欺騙他的感情
Dijkstra會很傷心的 （咦
-------------------
他不像鈴鐺人演算法是Label Correcting Algorithm
可以不斷的更改當前節點對起點距離的最小值
也就是他不會被負邊騙的意思！！
------------------
大概就是這樣 如果寫錯會自刪Q___Q
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.122.251.177
※ 編輯: andyisman 來自: 122.122.251.177 (08/08 07:46)