第七章 狄克斯特拉算法
戴克斯特拉算法 (又稱迪杰斯特拉算法), 使用了廣度優(yōu)先搜素解決賦權有向圖的單源最短路徑問題。 該算法存在很多變體, 戴克斯特拉的原始版本找到兩個頂點之間的最短路徑, 但是更常見的變體固定了一個頂點作為源節(jié)點然后找到該頂點到圖中所有其他節(jié)點的最短路徑, 產生一個最短路徑樹.
起點以左下角的紅點, 目標是右上角的綠點, 中間灰色的倒 L 型為障礙物王污。 藍色空圈表示 "暫定", 用以搜索下一步; 已經填充顏色的表示探訪過. 圖中顏色以紅到綠, 越綠表示離起點越遠。 所有節(jié)點都被均勻的探索泉唁。
換鋼琴
下面是書中的一個換鋼琴的例子:
[圖片上傳失敗...(image-9890be-1528173451438)]
這個圖中的節(jié)點是大家愿意拿出來交換的東西, 邊的權重是交換時需要額外加多少錢虹脯。 比如說拿樂譜換稀有黑膠唱片需要 5 美元, Rama(書中的人名)需要確定采用哪種路徑將樂譜換成鋼琴時需要支付的額外費用最少岳链。 因此, 我們可以使用戴克斯特拉算法。 別忘了, 戴克斯特拉算法包含四個步驟:
- 找出
最便宜的節(jié)點, 即可在最短時間內到達的節(jié)點; - 更新該節(jié)點的鄰居的開銷;
- 重復這個過程, 直到對圖中的每個節(jié)點都這樣做了;
- 計算最短路徑.
第一步: 找出最便宜的節(jié)點, 免費換海報, 還有比這更便宜的嗎, 沒有.
第二步: 計算前往該節(jié)點的各個鄰居的開銷
這個表格中很直觀, 以海報為父節(jié)點出發(fā), 換到低音吉他 30 美元, 架子鼓 35 美元
再次執(zhí)行第一步: 以樂譜為父節(jié)點的下一個最便宜的節(jié)點是黑膠唱片---5美元
再次執(zhí)行第二步: 更新黑膠唱片的各個鄰居的開銷
當然也很直觀, 以黑膠唱片為父節(jié)點, 換到低音吉他 15 美元, 換到架子鼓 20 美元署浩。 再以低音吉他換到鋼琴 20 美元, 架子鼓換到鋼琴是 10 美元揉燃。
因此, 我們可以得出結論, 樂譜 ---> 黑膠唱片 ---> 架子鼓 ---> 鋼琴這種兌換路線是最便宜的, 35 美元
實現(xiàn)
# coding: utf-8
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = "None"
processed = []
print(costs)
def find_lowest_cost_node(costs) :
low_costs = float("inf")
low_costs_node = None
for node in costs :
cost = costs[node]
if cost < low_costs and node not in processed :
low_costs = cost
low_costs_node = node
return low_costs_node
node = 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:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
print(costs)