數據結構和算法
基于《算法圖解》—Aditya Bhargava 和《數據結構》—嚴蔚敏

第7章 狄克斯特拉算法

上一章的廣度優先搜索，找出的是段數最少的路徑；
本章狄克斯特拉算法，找出的是最快的路徑。

7.1 使用狄克斯特拉算法
步驟：
第一步：找出最便宜的節點

從起點出發，前往節點A需要6分鐘，而前往節點B需要2分鐘。置于前往其他節點，先假設為不窮大。

第二步：計算經節點B前往其各個鄰居所需的時間。

經節點B可以找到前往節點A更短的路徑，只需要5分鐘。

對于節點B的鄰居，如果找到前往它的更短路徑，就更新其開銷：

• 前往節點A的更短路徑(從6分鐘縮短到5分鐘)。
• 前往終點的更短路徑(從無窮大縮短到7分鐘)。

第三步：重復

重復第一步：找出可能在最短時間內前往的節點。 已經對節點B執行了第二步，除節點B外，可在最短時間內前往的節點是節點A。

重復第二步：更新節點A的所有鄰居節點開銷。

可以發現前往終點的時間為6分鐘。

7.1.1
使用廣度優先搜索來查找兩點之間的最短路徑，指的是段數最少；
而在狄克斯特拉算法中，每段都分配了一個數字或權重，因此找出的是總權重最小的路徑。

狄克斯特拉算法的4個步驟：

• （1）找出最便宜的節點，即可在最短時間內前往的節點。
• （2）對于該節點的鄰居，檢查是否有前往它們的更短路徑，如果有，就更新其開銷。
• （3）重復這個過程，直到對圖中的每個節點都這樣做了。
• （4）計算最終路徑。

7.2 術語

• 狄克斯特拉算法用于每條邊都有關聯數字的圖，這些數字稱為權重(weight)。
• 帶權重的圖為加權圖(weighted graph)，不帶權重的圖為非加權圖(unweight graph)。
• 環：從一個節點出發，走一圈后又回到這個節點。繞環的路徑不可能是最短路徑。
• 無向圖意味著兩個節點彼此指向對方，其實就是環。在無向圖中，每條邊都是一個環。
• 狄克斯特拉算法只適用于有向無環圖(directed acyclic graph，DAG)。

7.3 換鋼琴例子
Rama想用自己的樂譜來換架鋼琴，那么需要確定哪種路徑將樂譜換成鋼琴時需要支付的額外費用最少。

使用狄克斯特拉算法可得到：

7.4 負權邊
如果有負權邊，就不能使用狄克斯特拉算法。
因為狄克斯特拉算法是這樣假設的：對于處理過的海報節點，沒有前往該節點的更短路徑。這種假設僅在沒有負權邊時才成立。
在包含負權邊的圖中，要找出最短路徑，可使用貝爾曼-福德算法。

7.5 實現
以下圖為例。

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

算法實現思路

#實現圖GRAPH：將節點的鄰居和前往鄰居的開銷存儲到散列表中。 graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2graph["a"] = {} graph["a"]["fin"] = 1 #fin指到終點graph["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 processed = [] #記錄處理過的幾點的數組，避免多次處理。

準備工作做好了，接下來實現算法。
圖4.2

#首先定義函數find_lowest_cost_node找出開銷最低的結點 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 = cost #就將其視為開銷最低的節點lowest_cost_node nodereturn lowest_cost_node#實現狄克斯特拉算法 node = find_lowest_cost_node(costs) #在未處理的節點中找出開銷最小的節點。 while node is not None: #這個while循環在所有節點都被處理過后結束cost = cost[node]neighbors = graph[node]for n in neighbors.key(s): #遍歷當前節點的所有鄰居new_cost = cost + neighbors[n]if costs[n] > new_cost: #如果經當前節點前往該鄰居更近costs[n] = new_cost #就更新該鄰居的開銷parents[n] = node #同時將該鄰居的父節點設置為當前節點processed.append(node) #將當前節點標記為處理過node = find_lowest_cost_node(costs) #找出接下來要處理的節點，并循環

7.6 小結

• 廣度優先搜索用于在非加權圖中查找最短路徑。
• 狄克斯特拉算法用于在加權圖中查找最短路徑。
• 僅當權重為正時狄克斯特拉算法才管用。
• 如果圖中包含負權邊，請使用貝爾曼-福德算法。

——持續修改完善中…

總結

以上是生活随笔為你收集整理的07-狄克斯特拉算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。