Dijkstra算法python实现
时间: 2023-07-29 16:14:53 浏览: 52
以下是Dijkstra算法的Python实现:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离字典,将起点的距离设为0,其它点的距离设为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 初始化堆,将起点加入堆中
heap = []
heapq.heappush(heap, [distances[start], start])
while heap:
# 弹出堆中距离最小的点
current_distance, current_node = heapq.heappop(heap)
# 如果当前点已经遍历过,跳过
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(heap, [distance, neighbor])
return distances
```
其中,`graph`是一个字典,表示图中的邻接表。每个键表示一个节点,每个值是一个字典,表示该节点的邻居及其边权重。例如,如果节点A有邻居B和C,且与B的边权重为2,与C的边权重为3,则`graph`应该是这样的:
```python
graph = {
'A': {'B': 2, 'C': 3},
'B': {},
'C': {}
}
```
`start`是起点节点。函数返回一个字典,表示每个节点与起点的最短距离。