python 基于堆结构的dijkstra算法代码
时间: 2023-11-09 20:05:52 浏览: 45
以下是Python中基于堆结构的Dijkstra算法代码:
```python
import heapq
def dijkstra_heap(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
(current_distance, current_vertex) = heapq.heappop(heap)
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
heapq.heappush(heap, (distance, neighbor))
return distances
```
其中,`graph`是一个字典,用于存储图的结构,`start`是起点。在`distances`字典中,我们将起点的距离设置为0,其余顶点的距离设置为正无穷。然后,我们将起点和起点到起点的距离(即0)放入堆中。在堆不为空的情况下,我们将堆中距离最小的顶点弹出,并将其与其邻居进行比较。如果通过当前顶点到达邻居的距离小于邻居当前的距离,则将邻居的距离更新为当前距离,并将邻居和新的距离放入堆中。最后,我们返回`distances`字典,该字典包含从起点到每个顶点的最短路径。