写一个 dijkstra
时间: 2024-05-05 09:15:42 浏览: 7
算法的 Python 代码
以下是一个简单的 Python 代码实现 Dijkstra 算法的示例:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离和前驱节点字典
dist = {node: float('inf') for node in graph}
dist[start] = 0
prev = {node: None for node in graph}
# 使用优先队列来存储节点和距离
pq = [(0, start)]
while pq:
(min_dist, curr_node) = heapq.heappop(pq)
# 如果当前节点已被遍历,则跳过
if min_dist > dist[curr_node]:
continue
# 遍历当前节点的邻居
for neighbor, weight in graph[curr_node].items():
# 计算到当前邻居的距离
distance = dist[curr_node] + weight
# 如果距离更短,则更新距离和前驱节点
if distance < dist[neighbor]:
dist[neighbor] = distance
prev[neighbor] = curr_node
heapq.heappush(pq, (distance, neighbor))
# 返回最短路径和距离
return dist, prev
```
该代码使用了优先队列来存储节点和距离,以便在遍历邻居节点时能够按距离的顺序处理它们。注释中有详细的说明。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)