dijkstra算法最短路径python代码
时间: 2023-08-01 11:07:57 浏览: 41
以下是使用Dijkstra算法求解最短路径的Python代码示例:
```python
import sys
def dijkstra(graph, start):
# 初始化距离字典,默认为无穷大
distances = {node: sys.maxsize for node in graph}
distances[start] = 0
# 记录已访问过的节点
visited = set()
while len(visited) < len(graph):
# 选择当前距离最小的节点
current_node = min((node for node in graph if node not in visited), key=lambda x: distances[x])
visited.add(current_node)
# 更新与当前节点相邻节点的距离
for neighbor, weight in graph[current_node].items():
distance = distances[current_node] + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
return distances
# 示例图的邻接表表示
graph = {
'A': {'B': 5, 'C': 2},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 2, 'B': 1, 'D': 2},
'D': {'B': 3, 'C': 2}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print("最短路径:")
for node, distance in distances.items():
print(f"从节点 {start_node} 到节点 {node} 的距离为 {distance}")
```
这段代码使用了邻接表表示图的结构,并利用Dijkstra算法计算从起始节点到其他节点的最短距离。在代码中,`graph`变量表示图的结构,`start_node`变量表示起始节点,代码会输出从起始节点到其他节点的最短路径。