写一个迪杰什特拉模板代码
时间: 2024-05-12 09:20:35 浏览: 13
以下是迪杰斯特拉算法的模板代码,你可以根据需要进行修改。
```python
import heapq
def dijkstra(graph, start):
"""
:param graph: 图的邻接表表示,graph[u] 是从节点 u 出发可以到达的节点及其对应的边权重
:param start: 起点
:return: 到每个节点的最短距离
"""
n = len(graph)
# 初始化距离数组,将 start 节点的距离设为 0,其余节点的距离设为正无穷
distance = [float('inf')] * n
distance[start] = 0
# 使用堆来优化查找最短距离节点的过程
heap = [(0, start)]
visited = set()
while heap:
(dist, node) = heapq.heappop(heap)
# 如果当前节点已经访问过,直接跳过
if node in visited:
continue
visited.add(node)
# 对从当前节点可以到达的节点进行松弛操作
for neighbor, weight in graph[node]:
new_distance = dist + weight
if new_distance < distance[neighbor]:
heapq.heappush(heap, (new_distance, neighbor))
distance[neighbor] = new_distance
return distance
```
注释中已经说明了每一步的含义,你可以根据需要进行更改和调整。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)