python最短路径
时间: 2023-08-16 21:15:55 浏览: 118
python编写的最短路径算法
5星 · 资源好评率100%
在 Python 中,你可以使用图算法中的 Dijkstra 算法来找到最短路径。下面是一个示例代码:
```python
import heapq
def dijkstra(graph, start):
# 创建一个字典,用于存储每个节点的最短距离
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 创建一个优先队列,用于存储待处理的节点
queue = [(0, start)]
while queue:
current_distance, current_node = heapq.heappop(queue)
# 如果当前节点已经处理过,则跳过
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(queue, (distance, neighbor))
return distances
# 示例图
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print(f"从节点 {start_node} 到各个节点的最短距离:")
for node, distance in distances.items():
print(f"{node}: {distance}")
```
这段代码使用了一个字典来表示图,其中每个节点对应一个字典,字典的键是该节点的邻居节点,值是与邻居节点之间的距离。`dijkstra` 函数接受一个图和一个起始节点作为参数,并返回从起始节点到其他节点的最短距离。在示例图中,起始节点是 'A'。运行这段代码将输出从起始节点到其他节点的最短距离。
阅读全文