大學學習資料結構那會，當時記得終于把 dijkstra 算法搞明白了，但是今天碰到的時候，大腦又是一片空白，于是我就又學習了下，把自己的了解寫下來，希望你也可以通過本文搞懂 dijkstra 算法。
dijkstra 已經 62 歲了，是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在 1956 年制造，并于 3 年後在期刊上發表，在 2001 年的采訪中[1]他說到：從鹿特丹到格羅甯根的最短路徑是什麼？實際上，這就是對于任意兩座城市之間的最短路問題。解決這個問題實際上大概隻花了我 20 分鐘：一天早上，我和我的未婚妻在阿姆斯特丹購物，累了，我們便坐在咖啡館的露台上喝咖啡，然後我就試了一下能否用一個算法解決最短路問題。正如我所說，這是一個 20 分鐘的發現。不過實際上，我在 3 年後的 1959 年才把這個算法發表在論文上。即使現在來看這篇論文的可讀性也非常高，這個算法之是以如此優雅，其中一個原因就是我沒用筆紙就設計了它。後來我才知道，沒用筆紙設計的優點之一是你不得不避免所有可避免的複雜問題。令我驚訝的是，這個算法最終成為我成名的基石之一。"
主要解決帶權圖的最短路徑問題，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。dijkstra 算法使用類似廣度優先搜尋的方法解決賦權圖的單源最短路徑問題。
廣度優先搜尋，這個應該很形象，記得在算法實作的時候使用隊列就可以了。賦權圖也好了解，就是邊上有權重值，可以了解為兩點之間的距離，單源最短路徑，就是一個已知的點到其他所有點的最短路徑。
當然了，單源最短路徑算法也不是隻有 dijkstra，還有 bellman-ford 算法或者 spfa 算法，在邊權非負時适合使用 dijkstra 算法，若邊權為負時則适合使用 bellman-ford 算法或者 spfa 算法。今天隻聊 dijkstra。
咱直接說優化後的思路，其實就是用到了小頂堆（優先級隊列）來比較哪一個點的距離最近，關于堆排序，可以參考堆的實作及工程應用。
從起點 s 開始，将與起點 s 直接相連的點，根據它與起點 s 的距離，加入到小頂堆中，堆頂那個點 s1 與起點 s 的距離 d1 一定是最近的，取出堆頂的點 s1 ，然後把與 s1 直接相連的點，根據它與 s 的距離（d1 + s1到這個點的距離），加入到小頂堆中，堆頂那個點 s2 與起點的距離就是最小的。
每次取出堆頂元素的時候，這個堆頂就是已确認的最近距離的點，把它加入已通路的集合中，防止無向圖的重複計算，這樣直到周遊完所有頂點，就找出了起點到所有點的最小距離。
是不是很簡單，就是廣度搜尋，加上貪心的思想，先找出起點 s 開始直接相連的點（廣度搜尋），然後找出與 s 第一個最近的點（貪心），從最近的點出發，再次廣度，再次貪心，就可以找出距離起點 s 第二個最近的點，直到全部搜尋完畢。
算法時間複雜度 <code>o(e+vlog(v))</code> ，e 是邊的數量，v 是定點的數量，vlog(v) 其實就是堆排序的時間複雜度。
算法時間複雜度 <code>o(e+v)</code> 鄰接矩陣的空間複雜度。
如果還不了解的話，多看幾遍下這個動圖：
為了簡化說明，我們使用鄰接矩陣來表示一個圖，圖中有 n 個頂點，标記為 1，2，...n，現在要求解起點 1 到所有其他點的最小距離。
以終為始，先定義一個儲存結果的最小距離的數組，<code>cost[n]</code> cost[i] 就是表示起點 1 到點 i+1 的最小距離，cost[0] = 0，起點 1 到它本身的距離是 0。這裡 i+1 是因為數組下标從 0 開始。
假如有 6 個頂點，使用鄰接矩陣來表示：
<code>adjacency_matrix[i][j] = c</code> 意思就是點 i+1 到 j+1 的成本是 c，加一的原因是數組的下标從 0 開始。
下面是我根據上述思路，實作的 dijkstra 算法，裡面有注釋，不難看懂：
純粹的記憶算法的實作其實沒有太大用處，算法最重要的是了解它的思路，以及學會靈活的運用，比如說從 a 到 b 中間最多經過 k 個節點的最小距離，你可以試着用 dijkstra 算法的思路來求解麼？假如有負數的權值，怎麼用 dijkstra 算法求解？
如果有問題，請留言賜教。
都看到這裡了，你不确定不關注一下嗎？????
[1]
在 2001 年的采訪中: https://zh.wikipedia.org/wiki/%e6%88%b4%e5%85%8b%e6%96%af%e7%89%b9%e6%8b%89%e7%ae%97%e6%b3%95