狄克斯特拉算法可以找出加權圖中前往X的最短路徑。

注意：
- 其只適用于有向無環圖
- 適用于正權邊，負權邊的將出錯（貝爾曼—福德算法適用于負權邊）

步驟：

找出當前最“便宜”的節點，即可在最短時間內前往的節點

對于該節點的鄰居，檢查是否有經當前節點前往他們的更短的路徑，如果有，經更新其開銷

重復這個過程，直到對圖中的每個節點都這樣做了

計算最終得路徑

實例：

# coding=utf-8# 圖表 graph = {} graph["start"] = {} graph["start"]["a"] = 6 # 開始節點的鄰居和鄰居的開銷 graph["start"]["b"] = 2graph["a"] = {} # a節點的鄰居和鄰居的開銷 graph["a"]["fin"] = 1 graph["b"] = {} # b節點的鄰居和鄰居的開銷 graph["b"]["a"] = 3 graph["b"]["fin"] = 5graph["fin"] = {} # 終點的鄰居和鄰居的開銷# 節點的開銷散列表 infinity = float("inf") costs = {} costs["a"] = 6 # 這時你可能找到更短的路徑，但沒有影響 costs["b"] = 2 costs["fin"] = infinity #print infinity# 父節點的散列表 parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None# 處理過的節點列表 processed = []# 查找開銷最小的節點 def find_lowest_cost_node(costs):lowest_cost = float("inf") # python中表示無窮大lowest_cost_node = None # 查找每個節點for node in costs:cost = costs[node]# 如果小于目前的最小開銷并且未處理，就替換if cost < lowest_cost and node not in processed: lowest_cost = costlowest_cost_node = node # 替換目前最小開銷的節點return lowest_cost_node # 返回目前最小開銷的節點node = find_lowest_cost_node(costs) # 未處理的節點中找到開銷最小的點 print 'lowest_cost_node:',node 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: # 如果經當前節點前往鄰居節點更近costs[n] = new_cost # 就更新該鄰居的開銷parents[n] = node # 同時將該鄰居節點的父節點更新為當前節點processed.append(node) # 將當前節點標記為已處理node = find_lowest_cost_node(costs) # 找出接下來要處理的節點print 'lowest_cost_node:',nodeprint "Cost from the start to each node:" print 'parents:',parents print costs

結果：

=========== RESTART: C:\Users\LiLong\Desktop\Algorithm\dixstrah.py =========== lowest_cost_node: b lowest_cost_node: a lowest_cost_node: fin lowest_cost_node: None Cost from the start to each node: parents: {'a': 'b', 'b': 'start', 'fin': 'a'} {'a': 5, 'b': 2, 'fin': 6} >>>

可以看出最短路徑：

start→2bstart→3astart→1fin

開銷是：6

---

參考：《算法圖解》—Aditya Bhargava
適合入門的看，講的很基礎，很多形象插圖

總結

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

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