用python语言写一段通用的Dijkstra算法,并标注每一行的注释,告诉我如何使用,列举至少三个例子
时间: 2024-06-03 07:07:03 浏览: 115
# 定义一个函数,参数为起点、终点和图
def dijkstra(start, end, graph):
# 初始化两个集合,一个为已处理节点,一个为未处理节点
processed = set()
unprocessed = set(graph.keys())
# 定义一个字典,存储每个节点到起点的距离
distance = {}
for node in graph:
distance[node] = float('inf')
distance[start] = 0
# 定义一个字典,存储最短路径上的前一个节点
previous = {}
# 当未处理节点集合不为空时循环
while unprocessed:
# 在未处理节点中找到距离起点最近的节点
current = min(unprocessed, key=lambda node: distance[node])
# 将当前节点加入已处理节点集合中
unprocessed.remove(current)
processed.add(current)
# 遍历节点的邻居,更新距离和前一个节点
for neighbor, weight in graph[current].items():
if neighbor in processed:
continue
new_distance = distance[current] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
previous[neighbor] = current
# 如果当前节点是终点,终止循环
if current == end:
break
# 如果终点不在已处理节点集合中,说明无法到达终点,返回空列表
if end not in processed:
return []
# 根据前一个节点字典,从终点往起点遍历,得到最短路径
path = [end]
while path[-1] != start:
path.append(previous[path[-1]])
return path[::-1]
# 示例1
graph1 = {
'A': {'B': 5, 'C': 2},
'B': {'D': 4, 'E': 2},
'C': {'B': 8, 'E': 7},
'D': {'E': 6, 'F': 3},
'E': {'F': 1},
'F': {}
}
print(dijkstra('A', 'F', graph1)) # ['A', 'C', 'E', 'F']
# 示例2
graph2 = {
'A': {'B': 1, 'C': 2},
'B': {'C': 1, 'D': 3},
'C': {'D': 1},
'D': {}
}
print(dijkstra('A', 'D', graph2)) # ['A', 'B', 'C', 'D']
# 示例3
graph3 = {
'A': {'B': 1, 'C': 2},
'B': {'C': 1, 'D': 3},
'C': {'D': 1},
'D': {}
}
print(dijkstra('A', 'E', graph3)) # []
阅读全文