Dijkstra算法求最短路径代码
时间: 2024-06-23 14:01:02 浏览: 10
Dijkstra算法是一种用于寻找图中两点之间最短路径的贪心算法,通常用于解决单源最短路径问题。以下是一个简单的Dijkstra算法的Python实现:
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') 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': 3, 'C': 4},
'B': {'A': 3, 'C': 1, 'D': 2},
'C': {'A': 4, 'B': 1, 'D': 5},
'D': {'B': 2, 'C': 5, 'E': 1},
'E': {'D': 1}
}
shortest_paths = dijkstra(graph, 'A')
print(shortest_paths) # 输出:{'A': 0, 'B': 3, 'C': 4, 'D': 5, 'E': 6}
```
在这个例子中,`graph`是一个字典,表示图的邻接矩阵(键是节点,值是另一个字典,表示与该节点相连的邻居及其边的权重)。`start`参数是开始节点。`dijkstra`函数会返回从起始节点到其他所有节点的最短距离。