帮我写一个Python代码,实现迪杰斯特拉算法
时间: 2023-03-13 20:51:23 浏览: 170
迪杰斯特拉算法代码实现
5星 · 资源好评率100%
# 示例代码
# 定义字典,其中键是节点,值为其到起点的距离
graph = {
'start': {'A': 6, 'B': 2},
'A': {'finish': 1},
'B': {'A': 3, 'finish': 5},
'finish': {}
}# 定义字典,其中键是节点,值为最短路径中节点的父节点
parents = {
'start': None,
'A': 'start',
'B': 'start',
'finish': None
}# 定义字典,其中键是节点,值为节点到起点的最短距离
costs = {
'A': 6,
'B': 2,
'finish': float('inf')
}# 找出未访问的节点中距离起点最近的节点
def find_lowest_cost_node(costs):
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# 执行迪杰斯特拉算法
processed = []
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['finish'])
阅读全文