權重圖與狄克斯特拉算法|Python實作

在前面，我們讨論了圖與廣度優先搜尋，解決了一個“找朋友”的問題。現在，讓我們想一想，我們把問題換成了“找地方”——我們想從一個地方到達另一個地方，也按照最短路徑到達——這樣的問題中，我們使用圖來建立模型時，會發現連接配接——也就是兩個地方之間的路——是有權重，或者說長度的。這種情況下，廣度優先搜尋就不起作用了——它隻能保證我們找到走過最少的連接配接數，而沒有考慮這些連接配接有長度的情況。下面我們來考慮這個問題。

1. 兩個術語

（1）.權重圖

就像上面所說，廣度優先搜尋适用于“連接配接沒有長度值”的圖，我們稱之為非權重圖。而連接配接存在長度值時，我們使用狄克斯特拉算法，此時的圖稱為權重圖，連接配接的長度值稱為權重。比如：

（2）.有向無環圖

之前我們介紹過有向圖和無向圖，其實無向圖就是一個環：

也就是無向意味着兩個節點互相指向對方。

當環這個結構存在于圖中，并且終點不在環中時，環隻會徒勞的增權重重。我們要讨論的狄克斯特拉算法适用于有向無環圖（DAG）。

2. 狄克斯特拉算法

前面示例展示的那個圖過于簡單，無法展現這個算法的所有細節。是以，這裡我們搭建一個複雜一點的圖，并且解釋這個圖的現實意義——這會讓我們發現狄克斯特拉算法的用處之大。

這裡，節點的意思很明确：某件樂器；而連接配接上的權重指的是用前者換取後者時我們需要加的錢。比如，用樂譜換唱片時我們需要另外支付5元，而換海報就不需要。狄克斯特拉算法能幫助我們快速找到如何花最少的錢，用樂譜換一架鋼琴。

在我們開始之前，我們先建立一張表格：

父節點	節點	開銷
樂譜	唱片	5
樂譜	海報
吉他	∞
鼓	∞
鋼琴	∞

這張表記錄了從樂譜到其他樂器所花的錢。由于我們剛開始，隻能準确的寫出樂譜的鄰居——海報和唱片的資訊，是以表格存在空白。

我們在表格的開銷中找到最小值。由于所有的權重都是正數，是以現在表格中的最小值一定就是所有路徑中的最小值！這個最小值是換取海報所花的錢：0元。

最小值連接配接起來的節點是海報，是以我們計算從樂譜到海報的鄰居所需的花費。我們的表格變成了

父節點	節點	開銷
樂譜	唱片	5
樂譜	海報
海報	吉他	30
海報	鼓	35
鋼琴	∞

由于我們确定了樂譜到海報最少花費0元，是以我們不去管他。也就是說，我們不去考慮處理過的節點。是以，目前最小開銷是樂譜到唱片，我們去看看唱片的鄰居，然後更新表格：

父節點	節點	開銷
樂譜	唱片	5
樂譜	海報
唱片	吉他	20
唱片	鼓	25
鋼琴	∞

重複上面的步驟，現在最小開銷是20，我們的表更新為

父節點	節點	開銷
樂譜	唱片	5
樂譜	海報
唱片	吉他	20
唱片	鼓	25
吉他	鋼琴	40

現在最小開銷是25，繼續更新表格：

父節點	節點	開銷
樂譜	唱片	5
樂譜	海報
唱片	吉他	20
唱片	鼓	25
鼓	鋼琴	35

除了鋼琴之外我們沒有其他節點了——這意味着我們找到了最便宜的價格，我們隻要畫35元就能在上面的交易關系中用樂譜獲得宜家鋼琴，這是狄克斯特拉幫我們找到的最便宜的價格。

負權重

狄克斯特拉算法是不是适用于一切有向無環圖呢？其實我們在說明這個算法的過程中做出了一點要求：沒有負權重。這是因為我們在表格中檢查完一個最小值後，就不在對其進行考慮了。但是負權重的出現要求我們考慮這些内容。

在包含負權重的圖張尋找最短路徑使用的算法是貝爾曼-福德算法，而我們的狄克斯特拉算法隻适用于正權重的有向無環圖。

3. 實作

我們先來建立整個權重圖的模型，為了表示權重，我們在散清單中建立一些散清單：

trading_networks = {}

trading_networks['樂譜'] = {}
trading_networks['樂譜']['唱片'] = 5
trading_networks['樂譜']['海報'] = 0

trading_networks['唱片'] = {}
trading_networks['唱片']['吉他'] = 15
trading_networks['唱片']['鼓'] = 20 

trading_networks['海報'] = {}
trading_networks['海報']['吉他'] = 30
trading_networks['海報']['鼓'] = 35

trading_networks['吉他'] = {'鋼琴':20}

trading_networks['鼓'] = {'鋼琴':10}

trading_networks['鋼琴'] = {}
           

這個散清單的具體結構：

{
'樂譜': {'唱片': 5, 
		'海報': 0}, 
		
'唱片': {'吉他': 15, 
		'鼓': 20},
		
'海報': {'吉他': 30, 
		'鼓': 35},
		
'吉他': {'鋼琴': 20}, 

'鼓': {'鋼琴': 10}},

'鋼琴':{}
}
           

我們可以很快的得到兩個節點之間的權重。

然後，我們建立一個開銷表并初始化。所謂開銷表，就是從起點到圖中某個節點所需的權重和。對于無法确定的開銷值，我們設定為無窮大：

inf = float('inf')

costs = {}

costs['唱片'] = 5
costs['海報'] = 0
costs['吉他'] = inf
costs['鼓'] = inf
costs['鋼琴'] = inf
           

同時我們還需要一個記錄父節點的散清單以及記錄處理過的節點的清單：

parents = {}

parents['唱片'] = '樂譜'
parents['海報'] = '樂譜'
parents['吉他'] = None
parents['鼓'] = None
parents['鋼琴'] = None

processded = []
           

完成準備工作後，我們來實作算法：

def get_exchange_path(parents,end):
	'給出交換路徑。'

	exchange_path = []

	try:
		while True:
			exchange_path.append(end)
			end = parents[end]
	except:
		pass	

	exchange_path.reverse()

	return exchange_path

def find_lowest_cost_node(costs,processded):
	'尋找目前未處理的最小開銷節點。'

	lowest_cost = float('inf')
	lowest_cost_node = None
	for node in costs:
		cost = costs[node]
		if cost < lowest_cost and node not in processded:
			lowest_cost = cost
			lowest_cost_node = node
	
	return lowest_cost_node

def dickstra_algorithm(trading_networks=trading_networks,\
						costs=costs,\
						parents=parents,\
						processded=processded,\
						end='鋼琴'):
	
	node = find_lowest_cost_node(costs,processded)
		
	while node is not None:
		cost = costs[node]
		neighbors = trading_networks[node]

		for n in neighbors.keys():
			new_cost = cost + neighbors[n]

			if costs[n] > new_cost:
				costs[n] = new_cost
				parents[n] = node

		processded.append(node)
		node = find_lowest_cost_node(costs,processded)

	print('交換最小花費：{}'.format(cost))

	path = get_exchange_path(parents,end)

	string = '交換順序：'
	for item in path:
		string = string + str(item) + ' '
	print(string)
           

在我們的模型上運作這些函數，可以看到結果

交換最小花費：35
交換順序：樂譜 唱片 鼓 鋼琴 
           

終于，我們可以給出順序了。