為什麼Dijkstra演算法每輪遞推能夠保證找到一個頂點的最短路徑？

01-03

初學圖論的一個問題。
每次遍歷未確定最短路徑的頂點集T，找到從v0到T中所有點中，當前路徑最短的那個頂點vk。為什麼能夠保證這個當前的路徑長度就一定是最終確定的最短的路徑長度？

好好看書的話這個問題應該不難理解吧，首先Dijkstra演算法成立的前提條件是不存在負權的邊，這意味任何一條路徑，從起點開始到路徑中每個點的距離都是依次遞增的。所以按照遞增的順序來依次計算出最短路徑也就是Dijkstra演算法了。

為了簡單起見，我們可以認為所有的邊權都是正值。如果有邊的權值為0，則這個邊的兩個頂點到源點的最短距離一定相等，可以把它們看成是同一個頂點，這樣只要證明了邊權值為正值的情況，也就能進一步推廣到有邊權值為0的情況。

當我們計算最短路徑的時候，源點到任意一個點的最短距離，要麼是源點到它的某條邊的長度，要麼是源點到另一個點的最短距離距離，再加上另一個點到這個點的邊的長度，寫成公式就是：

$d(i) = min{D(s, i), min_{j e i} d(j) + D(j,i)}$

注意到我們有 $D(j,i) > 0$ ，假如我們已經提前知道了各個d(i)的大小順序，那麼比該頂點的最短路徑距離更長的點就不用考慮了，改寫成：

$d(i) = min{D(s, i), min_{d(j) < d(i)} d(j) + D(j,i)}$

假想我們已經提前將d(i)排好了序，除了源點以外，最近的是 $n_0$ ，然後是 $n_1$ ，然後是 $n_2$ ，也就是

$d(n_0) le d(n_1) le d(n_2) ... le d(n_m)$

那麼就有：

$d(n_k) = min{D(s, n_k), min_{j < k} d(n_j) + D(n_j, n_k)}$

可以看到這個表達式是按傳統的方式進行遞推的，這種帶有最優子結構的遞推也叫做動態規劃。如果我們知道頂點距離的順序，就可以用這個表達式很容易地遞推出每個節點的距離了。

問題在於，我們並沒有提前知道節點的最短距離的大小順序。不過這有個很巧妙的方法可以解決。

假如說我們現在已經知道了最短距離最小的前k個節點 ${n_0, n_1, ..., n_{k-1}}$ ——特別的，k = 0的時候，這些節點的集合是個空集。當然它們的最短距離也根據上面的式子算了出來。我們希望接下來，通過這些信息找到 $n_k$ ，並且計算出 $d(n_k)$ 。

我們回到最早的式子中

$d(i) = min{D(s, i), min_{j e i} d(j) + D(j,i)}$

如果在求最小值的第二項當中，去掉一些項，那麼得到的結果有可能會比原表達式大，但不可能比原表達式小（因為是求最小值的運算）。也就是對 $i otin {n_0, n_1, ..., n_{k-1}}$ ，有

$d(i) le min{D(s, i), min_{j in {n_0, n_1, ..., n_{k-1}}} d(j) + D(j,i)}$

同時有

$d(n_k) = min{D(s, n_k), min_{j in {n_0, n_1, ..., n_{k-1}}} d(j) + D(j,n_k)}$

也就是說對於最後的 $n_k$ 來說，前面的式子會取等號。我們又知道 $n_k$ 是剩下節點中最短距離最小的，也就是

$n_k = arg min_i d(i)$

$= arg min_i min{D(s, i), min_{j in {n_0, n_1, ..., n_{k-1}}} d(j) + D(j,i)}$

第二個等號是因為我們將求最值表達式中不是最小的項替換成了比較大的項，而最小的項保持不變，因此最小值不變。

這個最後的表達式就是Dijkstra演算法。在實際使用的時候，注意到這個式子可以改寫成：

$min{D(s, i), min_{j in {n_0, n_1, ..., n_{k-1}}} d(j) + D(j,i)}$

$= min{d(n_{k-1}) + D(n_{k-1}, i), min{D(s, i), min_{j in {n_0, n_1, ..., n_{k-2}}} d(j) + D(j,i)}}$

第二項在上一輪就已經算出來了，所以每一輪只需要用最新加入的節點放縮一次就可以了。

直觀來說，如果我們已經求出了k個離源點距離最近的點，以及它們各自的距離，那麼到源點距離第k+1近的點，它到源點的最短路徑只能經過這前k個點——如果經過了其他點，那麼這個其他點顯然離源點更近，那這個點一定不是第k+1近了。既然只經過這前k個點，那麼只用這前k個點放縮就可以找到那個最短路徑了。再加上前k-1個點上一輪已經放縮過，所以每一輪只需要用新加入的節點進行放縮就行了。

https://www.quora.com/What-is-the-simplest-intuitive-proof-of-Dijkstra%E2%80%99s-shortest-path-algorithm

原因很簡單：如果你想到達其它沒有標記長度的節點，就必須經過那些已經被標記過長度的節點，所以。。。

因為每次選vertex的時候選的是label最小的vertex。然後所選vertex的所有連接的鄰居，都會把鄰居的label更新成最短的路徑的長度。

很簡單，因為每次循環都會增多一個保證已經找到最短路的點。

設當前路徑最短的頂點為Vu，距離為d。意味著V0到達T中其他頂點的距離大於d。那麼，假設要以這些頂點為「中轉站」，則V0到達Vu的距離肯定更加大於d。所以，當前最短的頂點的最短路徑就是d。

自己好好做作業，不要到知乎騙答案。