[其他] Dijkstra 演算法

[sansia (sansia)]

請問

Dijkstra 演算法，為何只有在每個邊的權重不為負數時才正確

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 124.8.243.139
→ CCWck       :不然可能會有loop
→ doom8199    :不是吧，那個演算法是針對 directed graph 在做的
→ doom8199    :D. Alg.中 會創一個 set S, 每做一輪，就會多塞一個
→ doom8199    :vertex，順便 reload S裡面元素的所有 cost
推 suhorng     :因為dijkstra每次在標點時每次都是取最小的來標
→ doom8199    :可以證明出那個集合 S 裡面所記錄的 cost，必然是
→ doom8199    :兩點間的  shortest path,但先決條件是 path cost>0
→ suhorng     :樓上抱歉Orz
→ doom8199    :                                              =
→ doom8199    :沒關係 ^^a
→ sansia      :doom8199 你說了半天只是把我說的重覆一次
→ sansia      :我問你為什麼不能為負數!!
推 andyisman   :因為他是屬於greedy的演算法阿
→ doom8199    :我沒重複原po說的阿，該演算法即使只做到一半
→ doom8199    :對 S所包的 subgraph 來說，其最佳路徑都有找出來
→ doom8199    :就是因為該演算法有這個很強的特性,才能保證其正確性
→ doom8199    :但你要 "證明" 此特性是否為 true，就是要用到 path
→ doom8199    :cost 不能小於0 這個條件才能證明出來
→ doom8199    :至於證明，一般演算法課本都會有
→ doom8199    :原po會問這問題，表示你連該演算法的 correctness
→ doom8199    :都無法說明清楚。那原po應當要以 "證明它" 來下手
→ Sfly        :要開燈才能看到原po說的
推 pobm        :兇個屁阿 問問題態度這麼差是怎樣