Dijkstra 算法代码
时间: 2023-06-12 08:05:59 浏览: 49
下面是使用Dijkstra算法求解单源最短路径的Python代码:
```python
import heapq
def dijkstra(graph, start):
pq = [] # 用于存储待访问的节点
heapq.heappush(pq, (0, start)) # 将起点加入堆中
visited = set() # 记录已经访问过的节点
distance = {node: float('inf') for node in graph} # 记录起点到各个节点的距离
distance[start] = 0 # 起点到自己的距离为0
while pq:
(dist, curr_node) = heapq.heappop(pq) # 取出距离最小的节点
if curr_node in visited:
continue
visited.add(curr_node)
for neighbor, weight in graph[curr_node].items():
if neighbor in visited:
continue
new_distance = distance[curr_node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
heapq.heappush(pq, (new_distance, neighbor))
return distance
```
其中,`graph` 是一个邻接表表示的图,`start` 是起点。函数返回一个字典,表示起点到各个节点的最短距离。