Re: [其他] Dijkstra 演算法

[suhorng ( )]

我覺得 doom 板友說得很明白 原PO可以不要那麼兇嗎 :(

假設 d[v] 代表當前從 s 到 v 中的最短距離，
且對於所有當前從 s 仍然無法到達的點 u, 有 d[u] = ∞

-

dijkstra 每次會從尚未標號的點中選出一個點 u 使得 d[u] 最小, 並將 u 標上永久標號
, 以 d[u] 為 s 到 u 的最短路距離. 接著對於所有 (u, v)∈E, 去做放鬆的動作.

既然 dijkstra 是標上「永久標號」, 亦即對於任意 v,u 滿足 v 比 u 早標號的條件而言
, 我們必須要求 v 不可能再被放鬆, 否則當我們為 v 標上永久標號時, d[v] 仍然不是最
短路.

把這個條件寫出來就是 d[v] <= d[u] + w(u, v). 所以僅當所有邊的權重非負時，才可以
保證 dijkstra 算法的正確性，否則 dijkstra 有可能求出錯誤的結果。

此外, 當所有邊的權重為非負時，因為我們每次是取 d[u] 最小的點 u 來標上永久標號,
所以必然會有 d[v] <= d[u].

-

應該任何講最短路算法的書籍都有詳細證明... 再查一下比較保險XDD

※ 引述《sansia (sansia)》之銘言：
: 請問
: Dijkstra 演算法，為何只有在每個邊的權重不為負數時才正確

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.217.35.125
推 andyisman   :相較之下 我該刪我的文了Q____Q
推 privatewind :原PO很明顯沒有搞清楚Dijkstra的原理，簡言之就是
→ privatewind :當負權重出現時，Dij演算法所努力維護的不變量會被
→ privatewind :破壞。
推 walkwall    :有負權重時  標點可能被修改  要修正或用BellmenFord
推 yueayase    :像Dijkstra這種greedy algorithm要注意演算法是否會
→ yueayase    :造成某些例外情形