Re: [其他] Dijkstra 演算法

[sansia (sansia)]

這個解釋我剛看的時候很滿意
不過過了兩天又不滿意了

greedy method 能夠騙過他的病不需要負數
不信你把你的例子全部加 1000000 讓權重全部變成正的
一樣可以騙過讓它誤入歧途

所以看來負數並沒有什麼特別不可以

至於有別的網友說什麼它的証明
我的確不知道
我沒學過演算法
(只寫過離散數學)


※ 引述《andyisman (愛死你了 -////////-)》之銘言：
: 舉個反例好了
:        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: 124.8.239.24
推 johnjohnlin :演算法正確性證明都是 [初始]->[維持]->[終止]
→ johnjohnlin :negative weight 會造成 [維持] 那階段不能證明
→ johnjohnlin :就像不能用歸納法證明 2^x>x^2 for x>0, x in N
→ yueayase    :但如果把所有權重,加上一個數字,使得所有權種非負
→ yueayase    :可能會找錯路徑