用python写出狄克斯特拉算法
时间: 2023-03-20 14:01:02 浏览: 84
狄克斯特拉算法是一种用于解决带有非负边权的最短路径问题的算法。以下是使用Python编写狄克斯特拉算法的示例代码:
```
import heapq
def dijkstra(graph, start):
# 初始化距离为无穷大,起点距离为0
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 使用堆优化的方式存储未访问过的节点
heap = [(0, start)]
while heap:
# 取出距离最短的节点
current_distance, current_node = heapq.heappop(heap)
# 如果当前节点已经访问过了,则跳过
if current_distance > distances[current_node]:
continue
# 遍历当前节点的邻居节点
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 如果新的距离更短,则更新距离
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
# 返回起点到其他所有节点的最短距离
return distances
```
以上代码实现了狄克斯特拉算法的核心逻辑,接受一个邻接表形式的图和起点作为输入,返回起点到所有其他节点的最短距离。可以将该代码保存在.py文件中,通过import语句引用并调用dijkstra函数即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)