给出Python代码
时间: 2023-11-19 10:14:09 浏览: 32
当然可以,以下是Dijkstra算法的Python代码:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离和前驱字典
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
previous_vertices = {vertex: None for vertex in graph}
# 初始化堆
vertices = [(0, start)]
heapq.heapify(vertices)
while vertices:
# 取出堆中最小距离的节点
current_distance, current_vertex = heapq.heappop(vertices)
# 如果当前距离已经大于记录的距离,则直接跳过
if current_distance > distances[current_vertex]:
continue
# 遍历当前节点的所有邻居
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# 如果新距离比记录距离小,则更新
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_vertices[neighbor] = current_vertex
heapq.heappush(vertices, (distance, neighbor))
return distances, previous_vertices
```
以上代码实现了Dijkstra算法,接受一个邻接字典表示的图和一个起始节点,返回一个距离字典和前驱字典。其中,邻接字典中每个键值对表示一个节点和它的所有邻居及边权重。