在我們尋找身邊的人際關(guān)系的時(shí)候老玛，可以采用上一篇的廣度優(yōu)先搜索來進(jìn)行查找演怎。當(dāng)我們走出門去十厢，想要到某個(gè)地方的時(shí)候，這種場景我們安排路徑就更加的適合使用 狄克斯特拉算法探橱。
狄克斯特拉算法是應(yīng)用于權(quán)值為 正 的 加權(quán)有向無環(huán)圖 尋找最短路徑的一種算法申屹。
算法過程
加權(quán)有向無環(huán)圖
什么是加權(quán)有向無環(huán)圖呢？形如：
這個(gè)就是我們的主角隧膏，加權(quán)有向無環(huán)圖哗讥。如果你的家住在 Start 處，你想出門去一趟 End胞枕，過程中的所有你能走的路徑都以箭頭的方式標(biāo)注在圖中杆煞，所有路徑的距離都以數(shù)字的方式標(biāo)注在路徑的邊上，那么你能找到一條最短的從Start到End的路徑嗎腐泻？
狄克斯特拉算法
我們跟著狄克斯特拉算法的過程决乎，來看狄克斯特拉算法的解決問題的思路。
我們需要一些工具贫悄，來完成這個(gè)算法：
- 一張記錄到達(dá)中間地點(diǎn)距離的表格（距離表）
- 一張記錄到達(dá)該地點(diǎn)的之前的一個(gè)節(jié)點(diǎn)的表格（父地點(diǎn)表）
- 一張記錄所有能走的路徑的表格（路徑圖）
-
站在 Start 處瑞驱，我們此時(shí)只有兩條路可以走：A、B窄坦，此時(shí)我們的這三個(gè)圖表分別是：
站在Start處.png -
繼續(xù)找唤反，我們的宗旨是，每次都根據(jù)距離表鸭津，找最短的路徑彤侍。比如現(xiàn)在，我們找完了Start逆趋，查看一下距離表盏阶。此時(shí)，距離表告訴我們闻书，此時(shí)表中名斟，我們“記錄在冊(cè)”的地點(diǎn)只有兩個(gè)脑慧，A、B砰盐，而這兩個(gè)地點(diǎn)最近的那個(gè)是B闷袒，距離只有3，所以岩梳，我們選擇去B囊骤。B地點(diǎn)能到達(dá)的點(diǎn)只有兩個(gè)：C、E冀值，此時(shí)的三張圖表分別為：
站在B處.png
解釋一下圖中的意思也物，距離表中，除了我們第一次確定距離的A列疗、B兩個(gè)點(diǎn)之外滑蚯，我們從路徑圖中又得到了可以經(jīng)由B到達(dá)的B點(diǎn)的兩個(gè)鄰居：C、E兩點(diǎn)作彤。最終的結(jié)果就是膘魄，我們從Start（最開始）經(jīng)由B點(diǎn)所到達(dá)的C、E兩點(diǎn)的距離分別是：
C：Start -> B -> C（3 + 1 = 4）（到達(dá)B點(diǎn)的距離3加上B點(diǎn)到C點(diǎn)的距離1）
D：Start -> B -> E （3 + 6 = 9）（到達(dá)B點(diǎn)的距離3加上B點(diǎn)到E點(diǎn)的距離6）
我們將這個(gè)距離寫入了距離表竭讳，就得到了現(xiàn)在的距離表创葡。而C、E兩點(diǎn)是從B點(diǎn)走過來绢慢，所以C灿渴、E兩點(diǎn)的父地點(diǎn)表都寫入對(duì)應(yīng)的B地點(diǎn)。
此時(shí)胰舆，B點(diǎn)所能到達(dá)的所有點(diǎn)都記錄在了距離表中骚露，所以B點(diǎn)的使命完成，我們把B點(diǎn)標(biāo)記了一個(gè) X 缚窿，表示已經(jīng)處理完畢棘幸。
3.此時(shí)我們站在了B點(diǎn)，并且將B點(diǎn)所能到達(dá)的地點(diǎn)都“記錄在冊(cè)”倦零。此時(shí)我們繼續(xù)尋找路徑误续。我們?cè)俅尾榭淳嚯x表（2中的距離表），此時(shí)扫茅，距離最短的點(diǎn)是C（因?yàn)锽點(diǎn)已經(jīng)標(biāo)記為已處理蹋嵌，所以C點(diǎn)的4的距離是最短的），所以葫隙，我們?nèi)サ紺點(diǎn)栽烂，C點(diǎn)能到達(dá)的點(diǎn)只有End，所以，站到C點(diǎn)之后腺办，我們繼續(xù)更新三個(gè)圖表：
跟上面一樣焰手，所有C點(diǎn)能到達(dá)的點(diǎn)，我們都記錄在冊(cè)了怀喉，所以册倒，C的使命完成了，我們把C標(biāo)記一個(gè) X磺送。
4.我們繼續(xù)尋找。還是老規(guī)矩灿意，我們依然查看距離表估灿，此時(shí)，距離表上最短的距離是到達(dá)A點(diǎn)的距離5缤剧，所以馅袁，我們來到A點(diǎn)。A點(diǎn)所能到達(dá)的是C荒辕、D兩點(diǎn)汗销，我們分別登記入冊(cè)，所以現(xiàn)在的三個(gè)圖表分別是：
由于之前我們已經(jīng)處理過C點(diǎn)抵窒，所以弛针，即使現(xiàn)在C點(diǎn)還可以到達(dá)，但是已經(jīng)不是最近的可到達(dá)距離了（C點(diǎn)到達(dá)的最短距離是之前的經(jīng)由B的距離4李皇，現(xiàn)在經(jīng)由A到達(dá)C的距離是5+2 = 7）削茁。所以我們就不再去記錄C了（不再記錄已經(jīng)處理過的點(diǎn)）。
5.我們繼續(xù)找掉房。還是查看距離表茧跋，此時(shí)，距離表中卓囚，能到達(dá)的最近的點(diǎn)是D點(diǎn)（注意：距離表中的距離指的都是從起點(diǎn)到達(dá)該點(diǎn)的距離瘾杭，是7）。此時(shí)我們來到D點(diǎn)哪亿，D點(diǎn)能到達(dá)的點(diǎn)是：C粥烁、End，此時(shí)我們登記入冊(cè)（C已經(jīng)處理過锣夹，不入冊(cè)）我們得到的三個(gè)圖表分別是：
C點(diǎn)已經(jīng)處理過了页徐，我我們就不再考慮經(jīng)由D點(diǎn)去到C點(diǎn)了。我們來看經(jīng)由D點(diǎn)到達(dá)End點(diǎn)银萍，此時(shí)变勇，距離表中，從Start可以到達(dá)End的距離已經(jīng)有了一個(gè)9，我們此時(shí)需要比較一下搀绣，經(jīng)由D到達(dá)End的距離是：7 + 4 = 11 < 9飞袋。距離表中的距離要小于現(xiàn)在這條經(jīng)由D點(diǎn)到End的路徑，所以链患，我們不用更新End點(diǎn)的路徑和父地點(diǎn)表巧鸭。但是D點(diǎn)所有能到到達(dá)的地方都已經(jīng)處理完了，所以我們給D打一個(gè)X麻捻。
-
我們繼續(xù)找纲仍。此時(shí)表中除了最終到達(dá)的點(diǎn)End之外，只有一個(gè)E點(diǎn)了贸毕。所以此時(shí)最近能到達(dá)的點(diǎn)就只有E了郑叠，我們來到E點(diǎn)。E點(diǎn)所能到達(dá)的點(diǎn)只有：End明棍。我們此時(shí)來更新一下距離表（比較距離乡革，看是否需要更新）：
站在E處.png
此時(shí)，我們可以看到摊腋，E點(diǎn)到達(dá)End點(diǎn)的距離是1沸版，所以經(jīng)由E點(diǎn)到達(dá)End點(diǎn)的距離是： 9（到達(dá)E點(diǎn)的距離）+ 1（E點(diǎn)到End點(diǎn)的距離） = 10 > 9（表中到達(dá)End點(diǎn)的距離），所以我們不用跟新這個(gè)距離跟父節(jié)點(diǎn)兴蒸，但是E點(diǎn)所能到達(dá)的所有鄰居節(jié)點(diǎn)已經(jīng)處理完畢了视粮，所以我們把E點(diǎn)標(biāo)記為 X。
最終橙凳，我們已經(jīng)處理完畢了圖中所有從Start到達(dá)End點(diǎn)所經(jīng)由的點(diǎn)馒铃。我們現(xiàn)在查看距離表，此時(shí)到達(dá)End的距離是9痕惋，所以最終所有路徑中能到達(dá)End點(diǎn)的最小距離就是9区宇。
還有一點(diǎn)，我們要找到這條路徑值戳。這點(diǎn)好辦议谷，我們查看最終的父地點(diǎn)表，End的父地點(diǎn)是C堕虹，我們此時(shí)記下： End -> C卧晓。我們?cè)诳碈的父地點(diǎn)是B，此時(shí)我們完善記錄：End -> C -> B赴捞。還沒有到Start逼裆，我們繼續(xù)找B的父地點(diǎn)，父地點(diǎn)是：Start赦政！我們終于找到頭了胜宇，我們記錄：End -> C -> B -> Start耀怜。此時(shí)，我們翻轉(zhuǎn)這條逆向回溯的路徑：Start -> B -> C -> End桐愉，這條路徑就是從Start到達(dá)End最短的路徑财破！
注意： 迪克斯特拉算法只能用于權(quán)值為正的有向無環(huán)圖。如果存在負(fù)的權(quán)值从诲，那么就會(huì)造成狄克斯特拉算法中的通過累加來找最小路徑的思想左痢。每次的距離只能增加，不能減少才行系洛。必須要是有向無環(huán)圖才行俊性，要不然找路徑的過程就會(huì)在環(huán)中無限的循環(huán)下去，永遠(yuǎn)出不來描扯。
算法實(shí)現(xiàn)
# -*- coding: utf-8 -*-
# @Time : 2018-12-27 12:59
# @Author : Jaedong
# @Version : 3.6
# @File : dijkstra_algorithm.py
# @Software: PyCharm
# 狄克斯特拉算法磅废，獲取加權(quán)有向無環(huán)圖中兩個(gè)點(diǎn)的最小距離
def dijkstra_algorithm(graph, start, end):
# 構(gòu)建一個(gè)從起點(diǎn)開始，記錄所有經(jīng)過節(jié)點(diǎn)的路程距離的距離表
distances = {}
# 構(gòu)建一個(gè)記錄某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)的散列表荆烈，方便路徑回溯
parents = {}
# 初始化 distances 和 parents
for neighbor in graph[start]:
distances[neighbor] = graph[start][neighbor]
parents[neighbor] = start
# 查漏補(bǔ)缺，需要確定到終點(diǎn)的距離竟趾，如果沒有的話就是不知道憔购，不直達(dá)的話就是無限大
if end not in distances:
distances[end] = float('inf')
parents[end] = None
# 用于記錄已經(jīng)計(jì)算完畢到它最短距離的節(jié)點(diǎn)
handled = []
node = get_lowest_cost(distances, handled)
while node is not None:
# 獲取到達(dá)節(jié)點(diǎn)的距離
distance = distances[node]
# 通過該節(jié)點(diǎn)可到達(dá)的節(jié)點(diǎn)（鄰居節(jié)點(diǎn)）
for neighbor in graph[node]:
# 通過節(jié)點(diǎn)到達(dá)其鄰居節(jié)點(diǎn)的距離等于到達(dá)該節(jié)點(diǎn)的距離加上該節(jié)點(diǎn)到其鄰居節(jié)點(diǎn)的距離
new_distance = distance + graph[node][neighbor]
# 如果該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)在記錄路程的表中，就看看是否更新一下到它的距離
if neighbor in distances:
# 如果通過該節(jié)點(diǎn)到達(dá)該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的距離 小于 其它途徑到達(dá)該鄰居節(jié)點(diǎn)的距離
# 就更新到達(dá)該節(jié)點(diǎn)鄰居節(jié)點(diǎn)的距離岔帽，使到達(dá)該鄰居節(jié)點(diǎn)的距離越小越好玫鸟，路徑就最優(yōu)
# 如果小于的話，就更新鄰居節(jié)點(diǎn)的父節(jié)點(diǎn)為該節(jié)點(diǎn)犀勒，也就是選取了到達(dá)該鄰居節(jié)點(diǎn)的
# 更好的路徑是通過該節(jié)點(diǎn)到達(dá)的這一條
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
parents[neighbor] = node
# 如果該節(jié)點(diǎn)的這個(gè)鄰居節(jié)點(diǎn)并沒有在距離表中屎飘，無需更新，就直接添加進(jìn)去
else:
distances[neighbor] = new_distance
parents[neighbor] = node
# 記錄處理過后的節(jié)點(diǎn)贾费，繼續(xù)往前走下去
handled.append(node)
node = get_lowest_cost(distances, handled)
# 更新了所有節(jié)點(diǎn)的到達(dá)最小距離钦购，那么到達(dá)end的最小距離就是distances表中end所對(duì)應(yīng)的值
distance = distances[end]
# 通過不斷的回溯的方式，得到end到達(dá)start的路徑褂萧，這樣押桃，就得到了start到達(dá)end的路徑
parent = parents[end]
paths = [parent, end]
while parent is not start:
paths.insert(0, parents[parent])
parent = parents[parent]
return distance, paths
# 獲取距離表中到達(dá)所需距離最短的節(jié)點(diǎn)
def get_lowest_cost(distances, handled):
shortest = float('inf')
shortest_node = None
for node in distances:
if distances[node] < shortest and node not in handled:
shortest = distances[node]
shortest_node = node
return shortest_node
# 構(gòu)建路徑圖，使用字典嵌套字典的方式（散列表嵌套散列表）
graph = {}
# 從起點(diǎn)開始导犹，起點(diǎn)可以到達(dá)兩個(gè)點(diǎn)：A唱凯、B
graph['Start'] = {}
# 起點(diǎn)到A點(diǎn)的距離是5 Start -> A
graph['Start']['A'] = 5
# 起點(diǎn)到B點(diǎn)的距離是3 Start -> B
graph['Start']['B'] = 3
# A可以到達(dá)兩個(gè)點(diǎn)：C、D
graph['A'] = {}
# ... ...
graph['A']['C'] = 2
graph['A']['D'] = 2
graph['B'] = {}
graph['B']['C'] = 1
graph['B']['E'] = 6
graph['C'] = {}
graph['C']['End'] = 5
graph['D'] = {}
graph['D']['C'] = 3
graph['D']['End'] = 4
graph['E'] = {}
graph['E']['End'] = 1
graph['End'] = {}
distance, paths = dijkstra_algorithm(graph, 'Start', 'End')
print('\n最短的距離是：{}, 路徑是： {}'.format(distance, paths))
結(jié)果是：
