證明
Invariant: 當一個 node 在 Dijkstra’s Algorithm 中被 extract-min 從 heap 中抓出來時，它和 source node () 的距離就是從 到此 node 的最短距離。
Proof by Induction (Fig. 1)
首先圈圈中只有裝 node 時，invariant 成立，距離和最短距離都是 。假設當圈圈中有 個 node 時成立。假設 node 為第 個被 extract-min 的 node，而經過 relaxation， 的 parent 會是 ，代表 。至此， 已確定，長度等於 到 的最短路徑。假設還有另一條到 的最短路徑通過 到 ，我們可以證明這條路徑不是最短路徑，因為根據三角不等式：，結合上面的結論 ，可證明出 因此通過 的這條路徑並非最短路徑，所以原本通過 的那條路確實是最短路徑。
Proof by contradiction (Fig. 2)
Invariant 不變，假設 node 為現在被 extract-min 抓出來的 node，但是反證法假設還有另一個 node 在到 的 shortest path 上。根據 invariant，，而 故 ，造成矛盾，故證明出不會有其他 node 在通往 的 shortest path 上，所以經過 relax 後確實會得到通往 的 shortest path。
Note
Dijkstra’s Algorithm 只適用於 edge weight 為正的 graph 的理由就在於上面兩個證明的不等式，這兩個不等式都會需要 edge weight 為正才會成立。
Figures
Fig. 1
Fig.2
Reference
- 台大電機 Algorithm Class 江蕙如 投影片