Python图算法之狄克斯特拉算法

秒速五厘米 2022-02-20 09:17 212阅读 0赞

可用于类似公交线路用时最短的案例。

**图算法之狄克斯特拉算法（Dijkstra’s algorithm），包含4个步骤：**  
(1) 找出“最便宜”的节点（权重最小），即可在最短时间内前往的节点。  
(2) 对于该节点的邻居，检查是否有从起点前往它们的更短路径，如果有，就更新其路径（开销）。  
(3) 将未处理节点中的“最便宜”的节点重复前面的过程，直到对图中的每个节点都这样做了。  
(4) 计算最终路径。

狄克斯特拉算法用于每条边关联的数字称为权重（weight）。  
带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。

要计算非加权图的最短路径，可使用广度优先搜索。要计算加权图的最短路径，可使用狄克斯特拉算法。

狄克斯特拉算法只适用于有向无环图（directed acyclic graph，DAG）。

**注意：**  
不能将狄克斯特拉算法用于包含负权边的图。因为狄克斯特拉算法对于处理过的节点，没有前往该节点的更短路径，而这种假设仅在没有负权边时才成立。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼—福德算法（Bellman-Ford algorithm）。

# 创建节点权重表
    graph = {}
    graph['start'] = {}
    graph['start']['a'] = 6			#边的权重
    graph['start']['b'] = 2
    
    graph['a'] = {}
    graph['a']['end'] = 1			#a邻居的权重
    
    graph['b'] = {}
    graph['b']['a'] = 3	 			#b邻居的权重
    graph['b']['end'] = 5
    
    graph['end'] = {}				#终点无邻居
    
    # 创建初始开销表
    infinity = float('inf')			#Python中正无穷大为float('inf')，负无穷大为float('-inf')
    costs = {}
    costs['a'] = 6
    costs['b'] = 2
    costs['end'] = infinity			#暂时未知，以无穷大暂代
    
    # 创建初始父节点表
    parents = {}
    parents['a'] = 'start'
    parents['b'] = 'start'
    parents['end'] = None 			#暂时未知
    
    # 创建已处理节点
    processed = []
    
    # 在未处理节点中查找开销最低的节点
    def find_lowest_costs_node(costs):
    	lowest_cost = infinity								#初始化最低开销为无穷大
    	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
    
    # 获取最低开销线路的开销
    def get_lowest_cost():
    	node = find_lowest_costs_node(costs)				#在未处理节点中找到开销最低的节点
    	while node is not None:								#只要还有未处理节点就继续循环
    		cost = costs[node]								#当前节点开销
    		neighbors = graph[node]							#当前节点邻居
    		for n in neighbors:								#循环邻居节点
    			new_cost = cost + neighbors[n]				#从起始到当前节点的邻居节点的开销
    			if costs[n] > new_cost:						#如果经当前节点前往邻居节点更近，则：
    				costs[n] = new_cost						#更新到该邻居节点的开销
    				parents[n] = node 						#将该邻居的父节点设置为该节点
    		processed.append(node)							#将该节点标记为已处理
    		node = find_lowest_costs_node(costs)			#继续查找下一个未处理的开销最低的节点，并循环
    	return cost											#打印最低开销
    
    # 获取开销最低线路
    def get_end_path(val):
    	for node in parents: 								#在最终线路的父节点表中查找指定节点的子节点
    		if parents[node] == val: 						#如果当前节点的父节点为指定节点，则：
    			path.append(node) 							#将当前节点添加为path的下个元素
    			val = node 									#将当前节点作为父节点表的值，以备后续查找
    	if val != 'end':									#防止无限递归
    		get_end_path(val)
    	end_path = '——>'.join(path)
    	return end_path
    
    if __name__ == '__main__':
    	lowest_cost = get_lowest_cost()						#获取最低开销线路的开销
    	print('最低开销为：' + str(lowest_cost))
    	path = ['start']									#路线初始节点
    	end_path = get_end_path('start')					#获取开销最低线路
    	print('最低开销路线为：' + end_path)

**结果为：**

最低开销为：6
    最低开销路线为：start——>b——>a——>end