请写出dijkstra算法的python代码
时间: 2024-03-31 14:15:08 浏览: 108
dijkstra算法代码
以下是dijkstra算法的python代码:
```python
import sys
def dijkstra(graph, start):
# 初始化
dist = {}
for node in graph:
dist[node] = sys.maxsize
dist[start] = 0
queue = []
for node in graph:
queue.append(node)
# 循环直到所有节点的最短路径都被计算
while queue:
# 找到距离开始节点最近的节点
min_node = None
for node in queue:
if min_node is None:
min_node = node
elif dist[node] < dist[min_node]:
min_node = node
# 获取最近节点的邻居节点
neighbors = graph[min_node].items()
# 更新距离开始节点的距离
for neighbor, weight in neighbors:
alt_path = dist[min_node] + weight
if alt_path < dist[neighbor]:
dist[neighbor] = alt_path
queue.remove(min_node)
return dist
```
其中,graph是字典,表示图中的节点和它们之间的边。节点是键,它们的邻居节点和边的权重是值。start是起始节点。
阅读全文