dijkstra算法源码
时间: 2024-01-22 08:01:06 浏览: 19
Dijkstra算法是一种解决带权有向图中单源最短路径问题的经典算法。以下是Dijkstra算法的源码实现。
```python
import sys
def dijkstra(graph, start):
# 初始化距离字典,存储每个节点到起点的距离
distance = {}
for node in graph:
distance[node] = sys.maxsize
distance[start] = 0
# 初始化已访问节点集合和未访问节点集合
visited = set()
unvisited = set(graph)
while unvisited:
min_node = None
# 找到未访问节点中距离最近的节点
for node in unvisited:
if min_node is None:
min_node = node
elif distance[node] < distance[min_node]:
min_node = node
unvisited.remove(min_node)
if distance[min_node] == sys.maxsize:
break
for neighbor, weight in graph[min_node].items():
new_distance = distance[min_node] + weight
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
return distance
# 示例图的邻接表表示
graph = {
'A': {'B': 5, 'C': 10},
'B': {'D': 3, 'E': 2},
'C': {'F': 6},
'D': {},
'E': {'F': 4},
'F': {}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print(distances)
```
以上代码实现了Dijkstra算法,通过邻接表表示图,并使用字典存储每个节点到起点的距离。算法从起点开始,逐步确定从起点到每个节点的最短距离,直到所有节点都被访问过为止。最后,返回每个节点到起点的最短距离。在示例图中,起点为A,输出结果为一个字典,表示A到其他节点的最短距离。