单向最短路径的python代码
时间: 2023-11-12 14:13:38 浏览: 35
以下是单向最短路径的Python代码,使用Dijkstra算法实现:
```python
import heapq
from collections import defaultdict
def dijkstra(graph, start):
distances = {node: float('inf') 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
# 示例代码
graph = defaultdict(dict)
graph['A']['B'] = 3
graph['A']['C'] = 2
graph['B']['C'] = 1
graph['B']['D'] = 5
graph['C']['D'] = 2
graph['D']['E'] = 4
distances = dijkstra(graph, 'A')
print(distances) # 输出 {'A': 0, 'B': 3, 'C': 2, 'D': 4, 'E': 8}
```
上述代码中,我们使用了优先队列(Python中的heapq模块)来实现Dijkstra算法。我们首先初始化一个distances字典来存储每个节点到起点的距离,初始值为无穷大。然后我们将起点的距离设置为0,并将其插入到优先队列中。在每次循环中,我们弹出距离起点最近的节点并更新其周围节点的距离。如果新的距离比原来的距离更短,则将其更新到distances字典中,并将其插入到优先队列中。最后,我们返回distances字典,其中每个节点的值为该节点到起点的最短距离。
在示例代码中,我们创建了一个简单的图,并使用起点'A'调用dijkstra函数。函数返回了一个distances字典,其中每个节点的最短距离已经计算出来。