帮我用python写一段实现Dijkstra算法的代码
时间: 2024-04-25 13:06:34 浏览: 144
以下是一个简单的 Python 实现 Dijkstra 算法的示例代码:
```
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
(cost, current_node) = heapq.heappop(pq)
if cost > distances[current_node]:
continue
for neighbor, neighbor_cost in graph[current_node].items():
new_cost = distances[current_node] + neighbor_cost
if new_cost < distances[neighbor]:
distances[neighbor] = new_cost
heapq.heappush(pq, (new_cost, neighbor))
return distances
# 示例
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}
}
print(dijkstra(graph, 'A'))
```
运行结果:
```
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
```
阅读全文