Dijkstra方法的python代码实现
时间: 2023-08-05 21:02:00 浏览: 37
以下是Dijkstra算法在Python中的代码实现:
```python
import sys
# 计算从起点start到各个点的最短距离
def dijkstra(graph, start):
# 初始化距离字典
dist = {node: sys.maxsize for node in graph}
dist[start] = 0
# 初始化未访问集合
unvisited = set(graph)
# 遍历所有节点
while unvisited:
# 找到距离最小的节点
curr_node = min(unvisited, key=lambda node: dist[node])
# 从未访问集合中移除
unvisited.remove(curr_node)
# 如果距离为无穷大,则说明不连通
if dist[curr_node] == sys.maxsize:
break
# 更新与当前节点相邻节点的距离
for neighbor, weight in graph[curr_node].items():
new_dist = dist[curr_node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
return dist
```
其中,`graph` 是一个字典,表示图的邻接表,键为节点,值为另一个字典,表示与该节点相邻的节点和边的权重。`start` 是起点节点。函数返回一个字典,表示从起点到各个节点的最短距离。如果某个节点不连通,则距离为无穷大。