用python语言写一段通用的Dijkstra算法,并标注每一行的注释,告诉我如何使用
时间: 2024-05-22 13:16:03 浏览: 83
# 定义一个函数,参数为图和起点
def dijkstra(graph, start):
# 初始化距离字典,将起点到起点的距离设置为0,其他节点的距离设置为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 初始化路径字典,将起点到起点的路径设置为空,其他节点的路径设置为None
paths = {node: None for node in graph}
# 创建一个列表,存储未处理的节点
unprocessed_nodes = [node for node in graph]
# 当未处理的节点列表不为空时
while unprocessed_nodes:
# 从未处理的节点中找到距离起点最近的节点
current_node = min(unprocessed_nodes, key=lambda node: distances[node])
# 从未处理的节点列表中移除当前节点
unprocessed_nodes.remove(current_node)
# 如果当前节点的距离为无穷大,则算法结束
if distances[current_node] == float('inf'):
break
# 对于当前节点的每个邻居节点
for neighbor, weight in graph[current_node].items():
# 计算起点经过当前节点到达邻居节点的距离
tentative_distance = distances[current_node] + weight
# 如果计算出的距离小于当前记录的距离,则更新距离和路径
if tentative_distance < distances[neighbor]:
distances[neighbor] = tentative_distance
paths[neighbor] = current_node
# 返回起点到每个节点的最短距离和路径
return distances, paths
# 现在可以使用这个函数来计算任何有向加权图的最短路径。只需要将图表示为字典,其中每个键都是一个节点,每个值都是一个字典,
# 其中每个键表示一个邻居节点,每个值表示到该邻居的权重。例如,以下是一个图的字典表示方式:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'D': 3, 'E': 2},
'C': {'F': 5},
'D': {'G': 1},
'E': {'G': 4},
'F': {'G': 2},
'G': {}
}
# 调用函数,传入图和起点
distances, paths = dijkstra(graph, 'A')
# 输出起点到每个节点的最短距离和路径
print(distances)
print(paths)
阅读全文