小白的算法初识课堂(part7)--狄克斯特拉算法
學習筆記
學習書目:《算法圖解》- 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∞
| 客廳 | 2 |
| 廁所 | 6 |
| 餐廳 | ∞\infty∞ |
我們看到客廳離小黃最近,前往客廳只需要2m。
- 第二步:計算由客廳前往其他鄰居所需的路程
| 客廳 | 2 |
| 廁所(更新) | 5 |
| 餐廳(更新) | 7 |
小黃找到了一條前往廁所更短的路,只需要5m;同時,它也找到了前往餐廳更短的路,只需要7m。因為我們找到了前往廁所和餐廳更短的路,所以我們在表中更新其開銷。
- 第三步:重復
重復第一步:找出除客廳節(jié)點以外的,可在最短路程內(nèi)前往的節(jié)點。小黃觀察到,除了客廳以外,可在最短路程內(nèi)前往的節(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é)點的列:
| 《數(shù)學之美》 | 《編程之美》 | 0 |
| 《數(shù)學之美》 | 《西瓜書》 | 5 |
| – | 鋼筆 | ∞\infty∞ |
| – | PS4手柄 | ∞\infty∞ |
| – | 移動硬盤 | ∞\infty∞ |
具體步驟實現(xiàn)
- 找出最便宜的節(jié)點
我們首先要找出圖中最便宜的節(jié)點,并確保沒有到該節(jié)點的更便宜的路徑。可以看到,最便宜的節(jié)點是《編程之美》節(jié)點,我們不需要花一分錢,就可以換取到。
- 計算前往該節(jié)點的各個鄰居的開銷
| 《數(shù)學之美》 | 《編程之美》 | 0 |
| 《數(shù)學之美》 | 《西瓜書》 | 5 |
| 《編程之美》 | 鋼筆(更新) | 30 |
| 《編程之美》 | PS4手柄(更新) | 35 |
| – | 移動硬盤 | ∞\infty∞ |
- 再執(zhí)行第一步
可以看到,除了《編程之美》節(jié)點以外,最便宜的節(jié)點是《西瓜書》節(jié)點。
- 再執(zhí)行第二步
| 《數(shù)學之美》 | 《編程之美》(已用) | 0 |
| 《數(shù)學之美》 | 《西瓜書》 | 5 |
| 《西瓜書》 | 鋼筆(更新) | 20 |
| 《西瓜書》 | PS4手柄(更新) | 25 |
| – | 移動硬盤 | ∞\infty∞ |
- 循環(huán)往復
更新后,我們發(fā)現(xiàn)下一個最便宜的是鋼筆,因此更新其鄰居的開銷:
| 《數(shù)學之美》 | 《編程之美》(已用) | 0 |
| 《數(shù)學之美》 | 《西瓜書》(已用) | 5 |
| 《西瓜書》 | 鋼筆 | 20 |
| 《西瓜書》 | PS4手柄 | 25 |
| 鋼筆 | 移動硬盤(更新) | 40 |
最后,除了終點,只剩下PS4手柄了,我們更新其鄰居的開銷:
| 《數(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)邊的圖中,要找出最短路徑,可使用另一種算法—貝爾曼-福德算法.
看不懂上面這句話沒關系,我們按照狄克斯特拉算法的流程畫兩個表格:
| 《數(shù)學之美》 | 《編程之美》 | 0 |
| 《數(shù)學之美》 | 《西瓜書》 | 5 |
| – | PS4手柄 | ∞\infty∞ |
找到最便宜節(jié)點《編程之美》,更新其鄰居的開銷:
| 《數(shù)學之美》 | 《編程之美》 | 0 |
| 《數(shù)學之美》 | 《西瓜書》 | 5 |
| 《編程之美》 | PS4手柄(更新) | 35 |
找到最便宜節(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'] = infinityparents散列表:
parents = {} parents['a'] = 'start' parents['b'] = 'start' parents['fin'] = Nonepython代碼:
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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 菜鸟裹裹怎么添加多个手机号
- 下一篇: 伐木累暗示速激12