Dijkstra算法是經(jīng)典的求解一個頂點(diǎn)到其他頂點(diǎn)的最短距離的算法抑胎。每次學(xué)習(xí)的時候總是覺得思路簡單明了古胆，但每當(dāng)要用到時何鸡，就忘記了實現(xiàn)的細(xì)節(jié)纺弊。歸根結(jié)底還是應(yīng)用的少。相信做地圖導(dǎo)航的應(yīng)該對其如數(shù)家珍骡男。另一個難記的是這個算法名字本身俭尖。Dijkstra有點(diǎn)違反通常意義的單詞拼寫邏輯。今天決心寫一篇文章洞翩，讓它好記，忘不掉焰望！
記名字
首先看算法的名字骚亿，Dijkstra中文名稱為“迪杰斯特拉”。如何記憶呢熊赖？首先要記住這個單詞開頭是字母D来屠，我想這個恐怕學(xué)過的人都能記住。然后呢，你會發(fā)現(xiàn)D后面緊跟著的居然是ijk俱笛。這三個字母可是寫循環(huán)時最常用的局部變量名稱了捆姜，在字母表中也是親兄弟(挨著)。記到這里實際上最難記的部分已經(jīng)搞定了迎膜。后面的stra對應(yīng)中文“斯特拉”泥技，是比較好記的。
記算法
下面再看算法本身的記憶磕仅。Dijkstra算法最核心思想就一句話:不斷找最經(jīng)濟(jì)的新目的地珊豹。
假設(shè)有十個頂點(diǎn)1-10，要計算頂點(diǎn)1到其余頂點(diǎn)的最短距離榕订。常規(guī)思維需要逐個計算頂點(diǎn)1到頂點(diǎn)2-10的最短距離店茶。雖然這樣在邏輯上很順，但并不符合圖的邏輯劫恒。按照圖的邏輯贩幻，可能頂點(diǎn)1僅與頂點(diǎn)10相聯(lián)，應(yīng)該先計算到頂點(diǎn)10的最短距離更方便两嘴。這也是這個算法比較“別扭”的地方丛楚，也是容易忘記的原因。
換句話說溶诞，Dijkstra算法實際上并不關(guān)注本次計算的最小距離是到哪個頂點(diǎn)的鸯檬。其僅關(guān)注本次所求之距離已經(jīng)是最小的了。做個類比螺垢，如果把頂點(diǎn)比作旅游景點(diǎn)喧务，起始點(diǎn)為出發(fā)位置，則算法首先考慮旅游的經(jīng)濟(jì)性枉圃，再考慮是否去了所有的地方功茴。
下面對Dijkstra算法按圖的邏輯進(jìn)行描述，會發(fā)現(xiàn)一切都順理成章孽亲。
- 設(shè)置起點(diǎn)v
- 審視參考以前去過的路徑坎穿，找出可以到達(dá)沒去過頂點(diǎn)的所有路徑
- 若有，則選擇其中代價最小的路徑返劲。并標(biāo)記本次去過的頂點(diǎn)玲昧，執(zhí)行步驟2
- 若沒有，則結(jié)束
采用這樣的策略可以保證每去一個頂點(diǎn)都是基于以前總結(jié)的最優(yōu)經(jīng)驗的篮绿。使得路徑的代價最小孵延。不知道現(xiàn)實中有沒有人這樣玩。
