學習過最短路徑問題的人都不會不知道Dijkstra算法酥夭。這個算法適用于解決無負權圖的單源（且不管是否有向）最短路徑問題册赛。這篇小文來談談如何理解這一算法盒犹。
這里首先給出一個Python 3的代碼實現(xiàn)（以下代碼出自Python Algorithms一書牵祟，略有改動）痪蝇。
from heapq import heappush, heappop
def dijkstra(G, s):
D, P, Q = {}, {}, [(0, None, s)]
while Q:
du, pu, u = heappop(Q)
D[u], P[u] = du, pu
for v in G[u]:
if v not in D:
heappush(Q, (du + G[u][v], u, v))
return D, P
Dijkstra算法可以從很多角度去理解。我個人覺得最便于理解和記憶的角度喻旷，是將其視為一個圖遍歷算法生逸。這從上面的代碼中就能夠看出來。遍歷節(jié)點的算法都需要記錄“前線”且预，也就是所有已經(jīng)訪問過但沒有“完全考察”的節(jié)點槽袄。不同的遍歷算法，記錄“前線”所用的數(shù)據(jù)結構也不同锋谐。比如遍尺，BFS使用的是FIFO的隊列，DFS可以使用FILO的棧涮拗；而上面的代碼使用的則是一個優(yōu)先隊列乾戏。（實際上，如果待解決的圖的所有邊的權重都為同一正值的話多搀，那么就可以用BFS來解決歧蕉。換言之，BFS算法可以視為Dijkstra算法的一個特例康铭，是可以用于（實際上是最佳的）解決無權圖的單源最短路徑的算法。）
那么赌髓，怎么直觀地去理解Dijkstra算法所表示的這一遍歷過程呢从藤？比如說催跪，我們要解決的問題如果可以表現(xiàn)為下面這幅圖——這是幅無向無負權圖，其中S點表示起點夷野，每條邊的權重就是標注在旁邊的數(shù)字——那么怎么去表現(xiàn)Dijkstra算法所設定的遍歷呢懊蒸？
這里需要耍一個思維上的小花招：我們把每條邊想象成真實的路徑，然后把權重想象成對應路徑的長度悯搔。然后假設站在起點S的是旋渦鳴人骑丸。在0時刻，旋渦鳴人首先將起點S涂成黑色（在上面代碼中表現(xiàn)為D[s], P[s] = 0, None）妒貌，然后沿每條從S點出發(fā)的路徑——在上圖里就是SA通危、SB、SC三條邊——派出一名影分身灌曙。這些影分身的速度都一樣菊碟，每前進1個長度需花費1個單位的時間，所以在時刻7在刺、9逆害、14，這三個影分身分別依次到達C蚣驼、B魄幕、A點。每個影分身到達自己的目的地時颖杏，都會檢查該點有沒有被涂黑纯陨；如果已經(jīng)被涂黑，說明有別的影分身走了一條更短的路徑來過這個點输玷，那么這個后到的影分身就完成了自己的使命队丝，不用再考察已被涂黑的點的后續(xù)節(jié)點，可以“噗”地一下化成青煙消失了欲鹏；如果沒有被涂黑机久，那么說明這個影分身走的是起點S到該點的最短路徑，記下現(xiàn)在的時刻（也就是所循路徑的長度赔嚎，也即到S點的距離膘盖，D[u] = du）以及上一個節(jié)點（P[u] = pu），把這一點涂黑尤误，最后朝每條未被涂黑的鄰點派出新的影分身侠畔。例如上面的例子里，時刻9時损晤，有一個從起點S出發(fā)的影分身會到達B點软棺。由于B此時還是白色的，說明S到B的最短路徑的長度為9尤勋。涂黑B點喘落，然后朝A茵宪、E兩點各派出一名影分身（之所以不往C點派影分身，是因為C點已經(jīng)在時刻7被另一個從S點出發(fā)的影分身涂黑了瘦棋，也就是已經(jīng)在D這個dict里了）稀火。注意從B點往A點出發(fā)的影分身將在時刻11（=9+2）到達，早于從S點出發(fā)往A點去的那個影分身（他將在時刻14到達）赌朋，所以等后者到達時凰狞，會發(fā)現(xiàn)A點已經(jīng)是黑色的了。如此重復沛慢，直到所有的影分身都消失了赡若，也即所有從S點能夠到達的點都涂成了黑色（遍歷），也就是“前線”中不再有仍在路上的影分身（while Q不再繼續(xù)）颠焦。這時候斩熊，所有被涂黑的點，都記錄下了涂黑的時刻（最短距離）和每一個中間節(jié)點（最短路徑）伐庭。
按照這種理解粉渠，那么算法中的優(yōu)先隊列其實可以看作是時間軸。每次往優(yōu)先隊列里push一個元素圾另，代表新派出一個影分身霸株；而每次從優(yōu)先隊列里pop出一個元素，則代表了某個影分身到達了其目的節(jié)點集乔。而且去件，這種思路還可以幫我們從直觀上理解Dijkstra算法的適用范圍：必須無負權邊，因為影分身所走路徑的長度不可能為負扰路；既可以是有向圖也可以是無向圖尤溜，影分身按照允許的方向走就行了。
以上就是我對Dijkstra算法的一點理解汗唱。希望能夠對學習算法的同學有點幫助宫莱。
