-
在之前的廣度優(yōu)先搜索中,可以找出了從A點到B點的最短路徑秤掌。
0-1 -
這是最短路徑闻鉴，因為段數(shù)最少——只有三段，但不一定是最快路徑瓶竭。如果給這些路段加上時間渠羞，你將發(fā)現(xiàn)有更快的路徑。
0-2 - 之前用了廣度優(yōu)先搜索荧恍，它找出的是段數(shù)最少的路徑（如第一個圖所示）如果你要找出最快的路徑（如第二個圖所示）送巡，該如何辦呢盒卸？為此，可使用另一種算法——狄克斯特拉算法（Dijkstra’s algorithm）
- 使用狄克斯特拉算法
1-1
其中每個數(shù)字表示的都是時間淮腾，單位分鐘谷朝。為找出從起點到終點耗時最短的路徑武花，你將使用
狄克斯特拉算法。
如果你使用廣度優(yōu)先搜索专钉，將得到下面這條段數(shù)最少的路徑。
1-2
這條路徑耗時7分鐘站叼。下面來看看能否找到耗時更短的路徑尽楔！狄克斯特拉算法包含4個步驟第练。
(1) 找出“最便宜”的節(jié)點，即可在最短時間內到達的節(jié)點呕寝。
(2) 更新該節(jié)點的鄰居的開銷婴梧，其含義將稍后介紹。
(3) 重復這個過程怔球，直到對圖中的每個節(jié)點都這樣做了浮还。
(4) 計算最終路徑钧舌。
第一步：找出最便宜的節(jié)點。你站在起點崭歧，不知道該前往節(jié)點A還是前往節(jié)點B撞牢。前往這兩
個節(jié)點都要多長時間呢？
1-31-4
前往節(jié)點A需要6分鐘，而前往節(jié)點B需要2分鐘畜挥。至于前往其他節(jié)點，你還不知道需要多長時間躯泰。
由于你還不知道前往終點需要多長時間麦向，因此你假設為無窮大（這樣做的原因你馬上就會明白）。節(jié)點B是最近的——2分鐘就能達到话告。
第二步：計算經節(jié)點B前往其各個鄰居所需的時間秀撇。
1-5
你剛找到了一條前往節(jié)點A的更短路徑呵燕！直接前往節(jié)點A需要6分鐘件相。
1-6
但經由節(jié)點B前往節(jié)點A只需5分鐘夜矗！
1-7
對于節(jié)點B的鄰居紊撕，如果找到前往它的更短路徑，就更新其開銷对扶。在這里浪南，你找到了：
- 前往節(jié)點A的更短路徑（時間從6分鐘縮短到5分鐘）；
- 前往終點的更短路徑（時間從無窮大縮短到7分鐘）骡送。
第三步：重復絮记！
重復第一步：找出可在最短時間內前往的節(jié)點怨愤。你對節(jié)點B執(zhí)行了第二步，除節(jié)點B外憔四，可
在最短時間內前往的節(jié)點是節(jié)點A。
1-8
重復第二步：更新節(jié)點A的所有鄰居的開銷甸赃。
1-9
你發(fā)現(xiàn)前往終點的時間為6分鐘埠对！
你對每個節(jié)點都運行了狄克斯特拉算法（無需對終點這樣做）〔锰妫現(xiàn)在，你知道：
- 前往節(jié)點B需要2分鐘襟沮；
- 前往節(jié)點A需要5分鐘昌腰；
- 前往終點需要6分鐘。
1-10
廣度優(yōu)先搜索查找的是兩點之間的最短路徑固灵，“最短路徑”的意思是
段數(shù)最少巫玻。在狄克斯特拉算法中祠汇，給每段都分配了一個數(shù)字或權重，因此狄克斯特拉算法找出
的是總權重最小的路徑徒扶。
對比
- 術語
狄克斯特拉算法用于每條邊都有關聯(lián)數(shù)字的圖姜骡，這些數(shù)字稱為權重（weight）屿良。
2-1
帶權重的圖稱為加權圖（weighted graph）尘惧，不帶權重的圖稱為非加權圖（unweighted graph）。
2-2
要計算非加權圖中的最短路徑啥么，可使用廣度優(yōu)先搜索悬荣。要計算加權圖中的最短路徑，可使用狄克斯特拉算法践叠。圖還可能有環(huán)嚼蚀，而環(huán)類似下面這樣。
2-3
2-4
3. 代碼實現(xiàn)
-
以下面的圖為例
3-1 -
要編寫解決這個問題的代碼，需要三個散列表察藐。
3-2
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}
# 創(chuàng)建開銷表的代碼如下：
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 存放父節(jié)點的字典
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 最后，你需要一個數(shù)組悴务，用于記錄處理過的節(jié)點讯檐，因為對于同一個節(jié)點，你不用處理多次别洪。
processed = []
# print(graph)
def find_lowest_cost_node(costs):
"在未處理的節(jié)點中找出開銷最小的節(jié)點"
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs)
while node is not None: # 這個while循環(huán)在所有節(jié)點都被處理過后結束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): # 遍歷當前節(jié)點的所有鄰居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: # 如果經當前節(jié)點前往該鄰居更近
costs[n] = new_cost # 就更新該鄰居的開銷
parents[n] = node # 同時將該鄰居的父節(jié)點設置為當前節(jié)點
processed.append(node) # 將當前節(jié)點標記為處理過
node = find_lowest_cost_node(costs) # 找出接下來要處理的節(jié)點挖垛，并循環(huán)
print(processed)
- 小結
- 廣度優(yōu)先搜索用于在非加權圖中查找最短路徑。
- 狄克斯特拉算法用于在加權圖中查找最短路徑送矩。
- 僅當權重為正時狄克斯特拉算法才管用哪替。
- 如果圖中包含負權邊，請使用貝爾曼-福德算法晌块。
