小朋友們好，大朋友們好！

我是貓妹，一名愛上Python編程的小學(xué)生。

和貓妹學(xué)Python，一起趣味學(xué)編程。

今日主題

咱們今天繼續(xù)學(xué)習(xí)圖的應(yīng)用，這些算法都是實際問題抽象出來的。

舉個例子吧！

下面6個城市，不同城市之間的距離不同。

如圖所示，請問如果從北京出發(fā)，到達海南，哪條路徑最短？

這就需要了解下迪杰斯特拉算法(Dijkstra)了。

迪杰斯特拉算法

假設(shè)我們需要計算下圖任意兩點之間的最短距離。

假設(shè)從a點開始，我們假設(shè)a到其他點的距離是無窮大。

第一步更新：將a起始的邊，如果距離比無窮大小，更新。

第二步更新：從a相鄰的結(jié)點中，找到一個距離最近的點，也就是c點，做類似操作。

到達d點的距離1+2<4，更新4為3。

到達f點的距離1+8<10，更新10為9。

如此反復(fù)，直到所有點都被訪問到。

這種算法就是迪杰斯特拉算法(Dijkstra)。

Python實現(xiàn)

代碼實現(xiàn)（完整代碼，見同名公眾號，次條推文）：

我們用一個字典來表示圖，字典中可以嵌套字典哦：

我們定義一個函數(shù)來實現(xiàn)核心算法：

11行：G表示圖，s表示起始結(jié)點

12~14行：該列表保存起始結(jié)點到本結(jié)點的距離，除了自身到自身是0外，其他都初始化為無窮大

16行：字典，路徑，從起始結(jié)點到本結(jié)點的最小路徑所經(jīng)過的前繼結(jié)點(上一個結(jié)點)

17行：集合，訪問過的結(jié)點

18行：優(yōu)先級隊里，實現(xiàn)功能為，從當(dāng)前結(jié)點出發(fā)的多條邊中，選取最小的一個

21行：循環(huán)數(shù)為結(jié)點數(shù)減1，這里的_表示不關(guān)心循環(huán)變量

22行，從當(dāng)前結(jié)點相鄰的結(jié)點和邊處理，一是看到相鄰結(jié)點的距離是否需要更新，二是選取下一個結(jié)點

24行：如果新的路徑d，比之前的路徑D[u]小

25行：更新D[u]，D[u]保存的是起始結(jié)點到本結(jié)點的最小距離

26行：添加結(jié)點u的前繼結(jié)點為v，也就是->v->u

27行：將距離，結(jié)點放入優(yōu)先級隊列。從已更新的結(jié)點中(路徑當(dāng)前最小)，以便選取下個結(jié)點為當(dāng)前結(jié)點

28行：代碼中有break，根據(jù)break退出當(dāng)前循環(huán)

29行：此時v的權(quán)值和最小，最小路徑，預(yù)選取它

30~32行：v沒有被訪問過，把它放入已訪問隊列

33~34行：如果有孤立結(jié)點，不和任意結(jié)點連接，會進入此分支，可先不關(guān)心這個邏輯

35行：返回D，P。D表示起始結(jié)點s到達本結(jié)點的最小距離，P表示s到達本結(jié)點的路徑。

函數(shù)調(diào)用：

運行結(jié)果：

第一行字典中的鍵為結(jié)點(abcdef)，值為a到本結(jié)點最小路徑。

第二行字典中的鍵和值都是結(jié)點。1的前繼結(jié)點是0,2的前繼結(jié)點是0，如此類推。

你學(xué)會了嗎？

這算法真讓人拍案叫絕??！

迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。

他是一名天才程序員，為計算機的發(fā)展做出了巨大的貢獻。

好了，我們今天就學(xué)到這里吧！

如果遇到什么問題，咱們多多交流，共同解決。

我是貓妹，咱們下次見！