用Python写一个Dijstra 最短路程算法
时间: 2024-10-03 21:00:33 浏览: 12
当然可以。Dijkstra's 算法是一种用于寻找图中两点之间最短路径的贪心算法,它适用于加权边且边的权重都是非负的情况。以下是使用 Python 实现 Dijkstra 算法的一个简单版本:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离字典,所有节点的距离都设为无穷大,除了起点为0
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# 优先队列(小顶堆),存储节点及其到起点的距离
queue = [(0, start)]
while queue:
# 获取当前距离最小的节点
current_distance, current_node = heapq.heappop(queue)
# 如果已经找到更短的路径,则跳过该节点
if current_distance > distances[current_node]:
continue
# 遍历当前节点的所有邻居
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 更新邻居节点的距离,如果新距离更短则更新并入队列
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 示例:
# 图表示为邻接字典,键是节点,值是另一个字典,表示与该节点相连的邻居及权重
example_graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
shortest_paths = dijkstra(example_graph, 'A')
print(shortest_paths) # 输出各节点到起始点'A'的最短路径距离
阅读全文