學習筆記
學習書目：《算法圖解》- Aditya Bhargava

---

文章目錄

• • • 狄克斯特拉算法
    • • 具體步驟實現(xiàn)
    • 術(shù)語
    • 跳蚤市場
    • • 具體步驟實現(xiàn)
      • 負權(quán)邊
    • python實現(xiàn)

---

狄克斯特拉算法

在上一個Blog中，我們用廣度優(yōu)先搜索找到了從家到公園換乘最少的路線，即家–1-->路–>A–3路–>E–5路–>公園。

但是有的時候，我們要尋找的是從家到公園耗時最短的路線，這時廣度優(yōu)先搜索就不頂用了，我們將會使用狄克斯特拉算法解決這個問題。

我養(yǎng)了一直兔子，它叫小黃，我在家里給小黃從它的窩到餐廳搭一個兔子專用通道：

假設小黃從始至終保持勻速前進，且到達一個地點不做停留。

試問，從窩到餐廳，小黃走哪條路線耗費時間最短？在這種情境中，這個問題也可以理解為，小黃走哪條路線的總路程最短？

如果用廣度優(yōu)先搜索，小黃可能會選窩–>廁所–>餐廳或者窩–>客廳–>餐廳，但是這兩條路線所的總長為7m，并不是最短路線。

下面我們用狄克斯特拉算法尋找最短路線。狄克斯特拉算法包含4個步驟：

(1) 找出“最便宜”的節(jié)點，即可在最短時間內(nèi)到達的節(jié)點。

(2) 更新該節(jié)點的鄰居的開銷，其含義將稍后介紹。

(3) 重復這個過程，直到對圖中的每個節(jié)點都這樣做了。

(4) 計算最終路徑。

具體步驟實現(xiàn)

• 第一步：找到最便宜的節(jié)點

現(xiàn)在，小黃蹲在自己的窩里，它前往客廳要2m，前往廁所要6m，至于其他節(jié)點，小黃現(xiàn)在不知道要多遠，對于這種不知道路程長短的節(jié)點，小黃先設置其長度為無窮大$\infty$

節(jié)點長度

客廳	2
廁所	6
餐廳	$\infty$

我們看到客廳離小黃最近，前往客廳只需要2m。

• 第二步：計算由客廳前往其他鄰居所需的路程

節(jié)點長度

客廳	2
廁所(更新)	5
餐廳(更新)	7

小黃找到了一條前往廁所更短的路，只需要5m；同時，它也找到了前往餐廳更短的路，只需要7m。因為我們找到了前往廁所和餐廳更短的路，所以我們在表中更新其開銷。

• 第三步：重復

重復第一步：找出除客廳節(jié)點以外的，可在最短路程內(nèi)前往的節(jié)點。小黃觀察到，除了客廳以外，可在最短路程內(nèi)前往的節(jié)點是廁所。

重復第二步：更新廁所節(jié)點所有鄰居的開銷。

節(jié)點長度

客廳	2
廁所	5
餐廳(更新)	6

更新后，小黃發(fā)現(xiàn)，前往餐廳只需要6m了。

小黃對每個節(jié)點都運行了狄克斯特拉算法(不需要對終點這樣做)，現(xiàn)在它知道了：

• 前往客廳節(jié)點只需要2m
• 前往廁所節(jié)點只需要5m
• 前往餐廳節(jié)點只需要6m

現(xiàn)在，小黃知道，最短路徑是從窩–>客廳–>廁所–>餐廳，總路程只要6m.

上一個Blog里，使用了廣度優(yōu)先搜索來查找兩點之間的最短路徑，那時“最短路徑”的意思是段數(shù)最少。在狄克斯特拉算法中，小黃給每段都分配了一個數(shù)字或權(quán)重，因此狄克斯特拉算法找出的是總權(quán)重最小的路徑。

術(shù)語

狄克斯特拉算法用于每條邊都有關聯(lián)數(shù)字的圖，這些數(shù)字稱為權(quán)重。帶權(quán)重的圖稱為加權(quán)圖，不帶權(quán)重的圖稱為非加權(quán)圖。

要計算非加權(quán)圖中的最短路徑，可使用廣度優(yōu)先搜索。要計算加權(quán)圖中的最短路徑，可使用狄克斯特拉算法。圖還可能有環(huán)，這意味著我們可從一個節(jié)點出發(fā)，走一圈后又回到這個節(jié)點。

值得注意的是，無向圖意味著兩個節(jié)點彼此指向?qū)Ψ?#xff0c;其實就是環(huán)。在無向圖中，每條邊都是一個環(huán)。狄克斯特拉算法只適用于有向無環(huán)圖。

跳蚤市場

假設我們小時候都參加過跳蚤市場，我們知道跳蚤市場中非常自由，大家可以以物換物，直接用錢購買物品，甚至是以錢+物換物的方式進行交易。

現(xiàn)在，我有本《數(shù)學之美》，我可以有以下交易選項：

上圖說的是，如果我想得到《編程之美》可以用《數(shù)學之美》去換，且不用多花一分錢；而得到《西瓜書》則要用《數(shù)學之美》再加5元去換取；而如果我想得到鋼筆就要用《西瓜書》再加15元去換…以此類推

現(xiàn)在我想用最少的代價得到移動硬盤，這個過程我將借助狄克斯特拉算法來完成，為了得到最終路徑，我還要在我的表中添加父節(jié)點的列：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》	0
《數(shù)學之美》	《西瓜書》	5
–	鋼筆	$\infty$
–	PS4手柄	$\infty$
–	移動硬盤	$\infty$

具體步驟實現(xiàn)

• 找出最便宜的節(jié)點

我們首先要找出圖中最便宜的節(jié)點，并確保沒有到該節(jié)點的更便宜的路徑。可以看到，最便宜的節(jié)點是《編程之美》節(jié)點，我們不需要花一分錢，就可以換取到。

• 計算前往該節(jié)點的各個鄰居的開銷

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》	0
《數(shù)學之美》	《西瓜書》	5
《編程之美》	鋼筆(更新)	30
《編程之美》	PS4手柄(更新)	35
–	移動硬盤	$\infty$

• 再執(zhí)行第一步

可以看到，除了《編程之美》節(jié)點以外，最便宜的節(jié)點是《西瓜書》節(jié)點。

• 再執(zhí)行第二步

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》(已用)	0
《數(shù)學之美》	《西瓜書》	5
《西瓜書》	鋼筆(更新)	20
《西瓜書》	PS4手柄(更新)	25
–	移動硬盤	$\infty$

• 循環(huán)往復

更新后，我們發(fā)現(xiàn)下一個最便宜的是鋼筆，因此更新其鄰居的開銷：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》(已用)	0
《數(shù)學之美》	《西瓜書》(已用)	5
《西瓜書》	鋼筆	20
《西瓜書》	PS4手柄	25
鋼筆	移動硬盤(更新)	40

最后，除了終點，只剩下PS4手柄了，我們更新其鄰居的開銷：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》(已用)	0
《數(shù)學之美》	《西瓜書》(已用)	5
《西瓜書》	鋼筆(已用)	20
《西瓜書》	PS4手柄	25
PS4手柄	移動硬盤(更新)	35

• 結(jié)果

通過狄克斯特拉算法，我只需要花35元加一本《數(shù)學之美》就可以換到移動硬盤啦！我的換取過程是：《數(shù)學之美》–>《西瓜書》–>PS4手柄–>移動硬盤

負權(quán)邊

如果發(fā)生了點意外，有個同學A現(xiàn)在立馬要用《西瓜書》,但它只有《編程之美》，所以他愿意用7元加《編程之美》換取西瓜書：

那么現(xiàn)在我有兩種選擇可以得到《編程之美》：

(1)不花一分錢換《編程之美》

(2)先花5元買《西瓜書》，再和A同學交易《編程之美》，那么我們將得到《編程之美》加2元

顯然方法2更好一些。

雖然我們可以這樣做，但是狄克斯特拉算法并不支持這樣的方式，如果有負權(quán)邊，就不能使用狄克斯特拉算法。因為負權(quán)邊會導致這種算法不管用。

這是因為狄克斯特拉算法這樣假設：對于處理過的《編程之美》節(jié)點，沒有前往該節(jié)點的更短路徑。這種假設僅在沒有負權(quán)邊時才成立。因此，不能將狄克斯特拉算法用于包含負權(quán)邊的圖。在包含負權(quán)邊的圖中，要找出最短路徑，可使用另一種算法—貝爾曼-福德算法.

看不懂上面這句話沒關系，我們按照狄克斯特拉算法的流程畫兩個表格：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》	0
《數(shù)學之美》	《西瓜書》	5
–	PS4手柄	$\infty$

找到最便宜節(jié)點《編程之美》，更新其鄰居的開銷：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》	0
《數(shù)學之美》	《西瓜書》	5
《編程之美》	PS4手柄(更新)	35

找到最便宜節(jié)點《西瓜書》，更新其鄰居的開銷：

父節(jié)點節(jié)點開銷

《數(shù)學之美》	《編程之美》(已用)(更新)	-2
《數(shù)學之美》	《西瓜書》	5
《編程之美》	PS4手柄	35

我們看到《編程之美》已經(jīng)被我們處理過了，這里卻對其進行了更新。在狄克斯特拉算法中這非常危險，因為節(jié)點一旦被處理，就意味著沒有前往該節(jié)點的更便宜的路徑，但是我們卻找到了更便宜的路徑。

python實現(xiàn)

我們以下面這幅有向圖為例，用python實現(xiàn)狄克斯特拉算法：

要編寫解決這個問題的代碼，需要三個散列表：

隨著算法的進行，我們還要不斷的更新散列表costs和parents.

現(xiàn)在我們來寫python代碼。

graph散列表：

graph = {} graph['start'] = {} graph['start']['a'] = 6 graph['start']['b'] = 2graph['a'] = {} graph['a']['fin'] = 1graph['b'] = {} graph['b']['a'] = 3 graph['b']['fin'] = 5graph['fin'] = {}

costs散列表：

#定義無窮大 infinity = float('inf') costs = {} costs['a'] = 6 costs['b'] = 2 costs['fin'] = infinity

parents散列表：

parents = {} parents['a'] = 'start' parents['b'] = 'start' parents['fin'] = None

python代碼：

processed = []def find_lowest_cost_node(costs):lowest_cost = float('inf')lowest_cost_node = Nonefor node in costs:cost = costs[node]if cost < lowest_cost and node not in processed:lowest_cost = costlowest_cost_node = nodereturn lowest_cost_nodenode = find_lowest_cost_node(costs) while node is not None:cost = costs[node]neighbors = graph[node]for n in neighbors.keys():new_cost = cost + neighbors[n]if costs[n] > new_cost:parents[n] = nodeprocessed.append(node)node = find_lowest_cost_node(costs)print(parents)

總結(jié)

以上是生活随笔為你收集整理的小白的算法初识课堂(part7)--狄克斯特拉算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。