python dijkstra求单源最短路径
时间: 2023-09-17 10:09:17 浏览: 52
Dijkstra算法是求解单源最短路径的经典算法之一,其基本思想是从起点开始,逐步扩展到离起点越来越远的节点,直到找到终点为止。以下是一个使用Python实现Dijkstra算法的示例代码:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离字典和已访问节点集合
dist = {node: float('inf') for node in graph}
dist[start] = 0
visited = set()
# 构建堆
heap = [(0, start)]
while heap:
# 取出堆顶元素
(distance, node) = heapq.heappop(heap)
# 如果节点已经被访问过,则跳过
if node in visited:
continue
# 将节点标记为已访问
visited.add(node)
# 更新与当前节点相邻的节点的距离
for neighbor, weight in graph[node].items():
if neighbor not in visited:
new_distance = dist[node] + weight
if new_distance < dist[neighbor]:
dist[neighbor] = new_distance
heapq.heappush(heap, (new_distance, neighbor))
return dist
```
其中,`graph`是图的邻接表表示,`start`是起点。这段代码使用了堆来实现优先队列,以提高效率。在实际应用中,可以根据需要进行一些修改,比如添加路径记录等功能。