1樓：天桃吃放
我按動態規劃思路的理解：
以標記第 個找到最短路的點為第 階段，以已經確定最短路的點及其衍生算出的最短路長度為狀態。在 階段中要根據已經確定的 個確定最短路的點及其最短路長度推出第 個得到最短路的點及其最短路徑及長度。
設 為已經找到最短路的點集（Marked）， 為還未找到最短路的點集（Unmarked），起點為 ，兩點間的某一路徑長度為 ，兩點間的最短路徑長度為 。
第 階段：
因為邊權重不小於零，所以 的最短路徑已知（），。
從第 階段到第 階段：
已有個確定最短路的點及其最短路長度，要對 中的某乙個點 找到從 到此的最短路路徑；
因為 、 ，所以這條路徑必定會包含一條連線 點集中一點和 點集中一點的邊，不妨設這條邊的連線的兩個點為 和 ，其邊權重為 。
則 ，如 要成為這個階段被標記最短路的點，應能找到路徑長度最優值，使固定 時 始終成立，思路就是直接找到遍歷任意 、、和各種路徑方案的 最小值作為 。
在 中的三個組成部分中， 為邊權重是固定的； 在固定情況下，由於，其最小值 和路徑方案已經在前面階段中找到；而 最小可取 ，即 為 或有 開銷路徑從到 的情況。所以對固定和 組合情況下的最小值為 。
接下來只要遍歷和 的各種可能組合，找到對任意和 的 最小值，這個值就是對任意 、和 的 最小值。這個遍歷和 的各種可能組合的過程就是 演算法中一直在做的工作（尋找從已經標記的點往外走一步的組合裡路徑長度最小的那個），得到最小值的即標記為找到最小路徑加入 ，其最短路徑經由到的最短路徑和邊 組成。
重複以上過程，直至所有目標點加入 ，演算法結束。
2樓：尹簡諧
給定乙個源點。把源點納入「已知點」集合。
此時「已知點」集合：｛源點｝
（「已知點」：目前已經知道的最短路徑的點，還知道它們的引出邊資訊。dist陣列的維護依賴並且只依賴於「已知點」引出邊資訊。）
顯然，和源點相連，邊最短的點就是第1近點，最短路徑就是這條邊。
把它納入已知點集合：｛源點、第1近點｝
（這裡是證明的關鍵）
到達第k近點的最短路徑，必不經過第k+1近點、第k+2近點……
因此，要確定到達第k近點的最短路徑，知道｛第0近點，…，第k-1近點｝（其實就是「已知點」）的引出邊資訊就足夠了，與後面的點無關。所以，根據這些「已知點」的引出邊資訊更新後的dist陣列裡，必包含第k近點的路徑長度，顯然陣列裡最小的就是。
回到第二步，到達第2近點的最短路徑上，只能經過第0近點（源點）、第1近點，必不可能經過第3近點、第4進點……總之與後面的點無關。所以，根據｛源點、第1近點｝資訊更新dist後，陣列最小值對應的點就是第2近點，把它納入「已知點」集合。
此時「已知點」集合：｛源點、第1近點、第2近點｝
第三步：找離源點第3近的點，並確定到達它的最短路徑。
以此類推……
第n步：找離源點第n近的點，並確定到達它的最短路徑
直到所有點都變為「已知點」，演算法結束。
3樓：自由老頭
我初學此演算法時也曾思考過這個問題，其實只要用三點就可以解釋的很清楚。
下面的內容沒有什麼嚴謹的數學證明，感覺對新人還是比較友好的:)
首先，設w（u，v）為邊（u->v）的權值，weight（u，v）為從u到v的最短路徑權和，
d（u）為演算法執行某一時刻起點到u點的最短距離，det（u）為演算法執行結束後起點到u的最短距離（即真實最短距離）。
①Dijkstra演算法要求所有的邊權均為非負數，不能有負權邊。
②三角不等式
det(v)<= det(u) +w(u,v)
這個很好理解，如果從起點到v的最短路徑中存在（u->v）邊，就取等於號，否則取小於號。用反證法，如果不滿足這個式子，那把det（v）更新為det(u) +w(u,v)更優，這與det（v）為真實最短距離的定義相矛盾。
③每次出堆時，出來的點（設為u）是當前d值最小的那個點，並且d(u) 必定等於det（u）。用反證法，假如堆中有別的某一點x到u的路徑更優，需要滿足d(x) +weight(x,u) =d(u) ，而且weight（x，u）>=0，所以一定有d(x) +weight(x,u) >=d(u)，與前面d(x) +weight(x,u)完畢。
4樓：Mithrandir
樓上 @靈劍 的回答已經把 Dijkstra 演算法的過程闡述的非常清晰了，我再來提供乙個更加直白的通過數學歸納法對遞推找到的確實是最短路徑的證明，權當拋磚引玉一下。
Dijkstra 演算法是乙個可以解決單一源點最短路徑問題的經典演算法，本質上是對廣度優先搜尋（BFS）的乙個推廣，只是把 BFS 維護的棧換成了優先佇列。
如果我們規定 G 為演算法所應用的圖，s 是源點，l(u,v) 是從點 u 到 v 的邊的長度，V 是圖中所有的點的集合，那麼 Dijkstra 演算法的過程則如下所示：
我們再將演算法找到的距離記為 ，從 到 的實際最短距離記為 ，若想要證明演算法找到的確實是最短路徑，我們需要證明對任意 ，在當前輪遞推結束時都有 。這等同於證明 ， 。我們可以運用數學歸納法，在假設當上一輪結束時如有 ，則本輪結束時 同樣成立。
: 因為 的大小會不斷增大，只有當 時 ，此時 。所以在 是演算法找到的是最短路徑。
: 我們需要證明若當 時演算法找到的是最短路徑， 時演算法找到的同樣是最短路徑。此時我們令 為當 時加進 的頂點，記 ，則 ，且 ， ，有 。
因此，我們只需要證明 ，即可得到 ， 。想要證明這一結論，我們可以通過反證法，假設存在一從 到 的最短路徑 ，使得
我們可以知道 一定不在 內結束，但同時部分組成 的頂點在 中。令 為第乙個在 中離開 的路徑， 為在頂點 結束的 的子路徑，則有
同時，因為 與 相鄰，而結束時最後乙個更新的頂點是 ，故 一定被演算法更新過。根據 Dijkstra 演算法， ，所以
因為 ，最後乙個被加進 的頂點是 ， 則並沒有被加進 ，我們可以得到
而又由於 ，我們發現 ，矛盾。所以 必等於 。因此，若當 是演算法找到的是最短路徑， 時演算法找到的同樣是最短路徑。
綜上所述，Dijkstra 演算法每輪遞推確實能夠保證找到乙個頂點的最短路徑。
5樓：Cakie
因為每次選vertex的時候選的是label最小的vertex。然後所選vertex的所有連線的鄰居，都會把鄰居的label更新成最短的路徑的長度。
6樓：
設當前路徑最短的頂點為Vu，距離為d。意味著V0到達T中其他頂點的距離大於d。那麼，假設要以這些頂點為「中轉站」，則V0到達Vu的距離肯定更加大於d。
所以，當前最短的頂點的最短路徑就是d。
7樓：靈劍
好好看書的話這個問題應該不難理解吧，首先Dijkstra演算法成立的前提條件是不存在負權的邊，這意味任何一條路徑，從起點開始到路徑中每個點的距離都是依次遞增的。所以按照遞增的順序來依次計算出最短路徑也就是Dijkstra演算法了。
為了簡單起見，我們可以認為所有的邊權都是正值。如果有邊的權值為0，則這個邊的兩個頂點到源點的最短距離一定相等，可以把它們看成是同乙個頂點，這樣只要證明了邊權值為正值的情況，也就能進一步推廣到有邊權值為0的情況。
當我們計算最短路徑的時候，源點到任意乙個點的最短距離，要麼是源點到它的某條邊的長度，要麼是源點到另乙個點的最短距離距離，再加上另乙個點到這個點的邊的長度，寫成公式就是：
注意到我們有 0" eeimg="1"/>，假如我們已經提前知道了各個d(i)的大小順序，那麼比該頂點的最短路徑距離更長的點就不用考慮了，改寫成：
假想我們已經提前將d(i)排好了序，除了源點以外，最近的是，然後是，然後是，也就是
那麼就有：
可以看到這個表示式是按傳統的方式進行遞推的，這種帶有最優子結構的遞推也叫做動態規劃。如果我們知道頂點距離的順序，就可以用這個表示式很容易地遞推出每個節點的距離了。
問題在於，我們並沒有提前知道節點的最短距離的大小順序。不過這有個很巧妙的方法可以解決。
假如說我們現在已經知道了最短距離最小的前k個節點——特別的，k = 0的時候，這些節點的集合是個空集。當然它們的最短距離也根據上面的式子算了出來。我們希望接下來，通過這些資訊找到，並且計算出。
我們回到最早的式子中
如果在求最小值的第二項當中，去掉一些項，那麼得到的結果有可能會比原表示式大，但不可能比原表示式小（因為是求最小值的運算）。也就是對，有
同時有也就是說對於最後的來說，前面的式子會取等號。我們又知道是剩下節點中最短距離最小的，也就是
第二個等號是因為我們將求最值表示式中不是最小的項替換成了比較大的項，而最小的項保持不變，因此最小值不變。
這個最後的表示式就是Dijkstra演算法。在實際使用的時候，注意到這個式子可以改寫成：
第二項在上一輪就已經算出來了，所以每一輪只需要用最新加入的節點放縮一次就可以了。
直觀來說，如果我們已經求出了k個離源點距離最近的點，以及它們各自的距離，那麼到源點距離第k+1近的點，它到源點的最短路徑只能經過這前k個點——如果經過了其他點，那麼這個其他點顯然離源點更近，那這個點一定不是第k+1近了。既然只經過這前k個點，那麼只用這前k個點放縮就可以找到那個最短路徑了。再加上前k-1個點上一輪已經放縮過，所以每一輪只需要用新加入的節點進行放縮就行了。
為什麼dijkstra演算法要用貪心？
Zha0q1 Dijksra較之大部分其他greedy的特別之處在於擴充套件的是global minimum。即every node to be poped from the pq has the shorttest path from the start node at that moment s...
每朵雲都下落不明。每輪月亮都不知所終。什麼意思？
魚非愚 雁非彥 雲，每一朵，每一刻，都和之前上一秒的它不同。月，每一天，美滋滋，都是全新的形狀。我們抬頭張望的那一刻，或欣喜，或悲傷，不變的是鎖在各自情緒裡的孤獨，所以我們抬頭，覺得，有云，有月，也是種陪伴。可是，每朵雲都下落不明，每盞月亮都不知所蹤。是片刻即永恆的哀傷。雲不復，月不復，心境不復。沒...
std list sort 用了什麼演算法？為什麼速度這麼快？
linux40 歸併的非遞迴？暈死 明明是不需要與待排資料等長的臨時空間的歸併，因為list在歸併的時候不需要臨時空間，這樣不但不用copy，甚至在中間步驟不用完全遍歷待排序列，簡直就是極大地優化了歸併排序。遞不遞迴都不重要。用迴圈寫歸併。處理offset時累不累。 邱浩 其實就是 歸併排序的非遞迴...