上篇部落格我們詳細的介紹了兩種經典的最小生成樹的算法，本篇部落格我們就來詳細的講一下最短路徑的經典算法----迪傑斯特拉算法。首先我們先聊一下什麼是最短路徑，這個還是比較好了解的。比如我要從北京到濟南，而從北京到濟南有好多條道路，那麼最短的那一條就是北京到濟南的最短路徑，也是我們今天要求的最短路徑。
因為最短路徑是基于有向圖來計算的，是以我們還是使用上幾篇關于圖的部落格中使用的示例。不過我們今天部落格中用到的圖是有向圖，是以我們要講上篇部落格的無向圖進行改造，改成有向圖，然後在有向圖的基礎上給出最小生成樹的解決方案。本篇部落格我們的思路與之前資料結構相關部落格的風格保持一緻，首先我們先給出迪傑斯特拉算法的原理以及詳細的示意圖，然後根據這些示意圖給出具體的實作方案。
一、迪傑斯特拉算法原了解析
在部落格的第一部分，我們不談任何與代碼相關的内容，隻談迪傑斯特拉算法的原理以及生成最短路徑的具體步驟。下方我們會給出迪傑斯特拉算法的計算最短路徑的每一步，并給出每一步具體的說明。廢話少說，進入本部分的主題。
1、有向帶權圖
本篇部落格依然采取我們之前用的圖的結構。不過我們本篇部落格使用的是有向圖。下方這張圖就是是我們之前使用的無向圖轉換過來的，隻是給之前的圖的邊添加的具體的方向，其他的并為改動。由無向圖轉換後的有向圖如下所示，我們将在下方的圖的基礎上計算出從A到D的最短路徑。
2.迪傑斯特拉算法的具體步驟
下圖就是求上圖中A->D的最短路徑時使用迪傑斯特拉算法的具體步驟。迪傑斯特拉算法主要核心思想是由起始結點開始，慢慢的由尾結點擴散。直到擴充到尾結點位置。下方我們将根據每個步驟給出具體的介紹：
-
（1）與起始結點A直接相連的點是B和F， 即A->B的距離為10，A->F的距離為11, 是以我們選擇A->B這個路徑。
-
（2）選擇B結點後，我們開始探測與B相連的結點，即A->B->G路徑長度為26，A->B->I路徑長度為22，A->B->C路徑長度為28，這三個與上一步留下的A->F（11）相比，A->F（11）的距離最短，是以接下來要探測與F相連的結點。
-
（3）F可到達的點是G和E，是以A->F->G的距離為27，A->F->E的距離為37。因為A->F->G(27) 大于A->B->G(26)這個路徑，是以由A到G的路徑我們依然選擇A->B->G(26)這個路徑。從A->B->G（26），A->B->I（22）,A->B->C（28）, A->F->E（37）。中選出最短那個距離就是A->B->I（22），是以我們将I作為我們下次探測的結點。
-
（4）與I相連的就是D結點，是以我們容易計算出A->B->I->D這條路徑的長度為22+21=43。從A->B->I->D（43）, A->B->G（26）, A->B->C（28）, A->F->E（37）這些路徑中我們還是選擇最小的那一個，不難看出A->B->G（26）這條路徑在上述路徑集合中最小，是以我們将G結點作為下次路徑的探測對象。
-
（5）G可到達的結點是H和D, 是以我們可以得到兩條新的路徑A->B->G->H（26+19=45）和A->B->G->D（26+24=50），因為A->B->G->D(50)這條路徑的長度要大于A->B->I->D（43）這條路徑的長度，因為這兩條路徑都是從A到D，是以我們選擇較小的A->B->I->D（43）路徑。從A->B->G->H（45），A->B->I->D（43）, A->B->C（28）, A->F->E（37）這幾條路徑中我們依然選擇最小的那條路徑。從上面這幾條資料我們不難看出 A->B->C（28）這條路徑最短，是以我們下次要探測的點是C點。
-
（6）C點可以到達的點隻有D點，是以我們可以得到一條新的路徑A->B->C->D, 路徑長度為50。因為從A到達D的路徑還有A->B->I->D（43），而A->B->C->D(50)這條路徑的長度要大一些，A到D點的路徑依然選擇A->B->I->D（43）。C結點探測完畢，我們從A->B->G->H（45），A->B->I->D（43）， A->F->E（37）幾條候選路徑中依然選擇最小的那一個。不難看出 A->F->E（37）這條路徑最小，是以下一步我們要探測E結點。
-
（7）E結點可以到達的點為H和D，是以A->F->E(37)這條路徑可以延伸為A->F->E->H(44)和A->F->E->G(57)兩條邊。因為A到H的路徑還有一條為A->B->G->H（45），而我們剛生出的這一條要小于之前的那一條，是以A到H的路徑更新為A->F->E->H(44)。而A->F->E->G(57)這條A到D的路徑要比A->B->I->D（43）要大，是以不進行更新，A到D的路徑依然采用A->B->I->D（43）。經過這一步後我們将A->F->E->H(44)和A->B->I->D（43）進行比較，較小的路徑為A->B->I->D（43），而D節點又是我們的終點，是以A到D的最短路徑為A->B->I->D（43）。
3、迪傑斯特拉算法的資料表示
上面是我們使用圖形的方式給出了迪傑斯特拉算法的具體步驟，接下來我們會把上面的步驟轉換成資料的表示方式，以便于我們使用程式進行計算。下方就是上面這些示意圖的的完整的資料表示。下方矩陣中的資料标志着起始節點到該節點的距離。由上到下，以此增加距離的大小，而最上面一排的紅色字母，标示着該結點的前驅。下方我們在給出每一個行資料的詳細介紹。
-
第一行資料記錄了A->B和A->F的資訊，當然A->A的距離為0。其他尚不可達的點為-1。
-
第二行在第一行資料的基礎上證據了A->B->C, A->B->G, A->B->I的距離資訊，因為從第一行數的比較我們可以知道，A->B的距離要小于A->F的距離，是以我們的最短路徑要向着A->B->?上發展。
-
第三行的資料則是在第二行的資料上得到的，從第二行資料上我們容易看出，A->F(11)要比A->B->(C, G, I)都要小，是以我們的最短路徑要向着A->F->?的放心發展。是以我們找到了A->F->E(37)和A->F->G(28)這條路徑。因為A->B->G(26)小于A->F->G(28)，是以A到G的路徑不進行更新。
-
第四行的資料則是第三行資料的延伸，我們可以知道A->B->I（2）在目前所有延伸的路徑中最小，是以我們要向着A->B->I->? 方向發展。是以我們找到了A->B->I->D(43)這條路徑。
-
以此類推……
其實上圖就是我們之前原理圖的資料表示，接下來我們就要根據這些原理圖和資料圖來給出我們的代碼實作，當然我們還是使用Swift語言來實作。
二、迪傑斯特拉算法的具體實作
1.上述原理總結
上面說這麼多，簡單的總結一下，上面整個過程無非就是下面這兩步的循環，而循環結束的條件就是最短路徑延伸到結束路徑即可，也就是我們本例中的D點。
-
第一步：比較已經發展的所有路徑，找出目前最短的路徑。
-
第二步：在上一步找到的最短路徑的基礎上發展新的路徑，然後重複上一步，直到延伸到end節點為止。
經過這麼一分析，在給出具體的代碼實作就顯得簡單多了，我們的程式整體上來說就是一個循環，裡邊包含着上面這兩步。
2.具體代碼實作
分析完原理後，接下來我們就要開始實作我們的代碼了。下方就是我們整個代碼的具體實作。當然，我們的圖結構是以鄰接連結清單的形式存儲的有向聯通圖。具體代碼實作如下所示：
（1）路徑結構的存儲
我們先建立一個DistanceInfo類，該類中記錄了一些距離資訊。previousNoteIndex字段存儲的是目前節點的前驅節點的索引，預設為-1。而distance存儲的就是起始結點到該節點的距離，預設是最大距離。而isInPath則标記該結點是否位于已生成路徑的上，如果是的話就是true, 如果不是就是false，預設是false。
（2）代碼的整體結
下方代碼塊就是我們迪傑斯特拉算法代碼實作的整體結構。首先我們會建立一個distanceInfos數組，數組中元素的個數就是圖的結點的個數。其中存儲的是DistanceInfo的對象，每個數組索引對應的DistanceInfo對象中存儲的資訊就是起始結點到該結點的距離資訊。首先我們對起始結點的DistanceInfo對象進行初始化。
緊接着下方這個循環就是我們上面所說的循環，循環結束的條件就是将最短路徑延伸到end結點。循環中主要有兩步，第一步是在目前循環的index對應的結點上發展新的路徑，第二步就是在這些發展的路徑中尋找最短路徑，在這個新最短路徑的基礎上再次發展新的路徑。
（3）發展新的路徑
接下來我們來看一下countCurrentNoteAllDistance()方法中的代碼，也就是發展新的路徑的代碼。主要就是周遊鄰接連結清單上目前索引所連的連結清單上的資料，将這些資料所對應的結點添加到我們的路徑上。往路徑上添加新的結點是要注意一點，比如A->D是100， 之前B->D是80，如果現在的路徑要比之前的路徑要大就不更新，反之就更新我們距離資訊數組中的DistanceInfo對象。具體代碼如下所示：
（4）、尋找最小路徑
下方代碼就是尋找目前已發展的所有路徑中最短的那條路徑，主要還是對DistanceInfo數組的操作。下方代碼，找到最短路徑後，并把最短路徑的索引進行傳回。
上方就是我們迪傑斯特拉算法代碼實作的核心代碼。
三、測試用例
實作完代碼後，我們就要對代碼進行測試了。下方就是我們的測試用例，該測試用例中建立的圖是有向連通圖，并且要求出節點A->D的最短路徑。
上述測試用例的輸入結果如下：
今天的部落格就先到這兒，本篇部落格所涉及的Demo也将會在github上進行分享，分享位址如下：
github分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/ShortestPathDijkstra
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]