Dijkstra方法的代码实现,给出可运行代码和结果
时间: 2024-02-25 21:56:18 浏览: 17
以下是Dijkstra算法的Python实现。假设图中每条边的权重均为正数。
```python
import heapq
def dijkstra(graph, start):
# 初始化距离和前驱节点
dist = {node: float('inf') for node in graph}
dist[start] = 0
prev = {node: None for node in graph}
# 用堆优化的Dijkstra算法
heap = [(0, start)]
while heap:
(d, node) = heapq.heappop(heap)
if d > dist[node]:
continue
for neighbor, weight in graph[node].items():
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
prev[neighbor] = node
heapq.heappush(heap, (new_dist, neighbor))
return dist, prev
```
我们可以使用以下代码进行测试:
```python
graph = {
'A': {'B': 10, 'C': 3},
'B': {'C': 1, 'D': 2},
'C': {'B': 4, 'D': 8, 'E': 2},
'D': {'E': 7},
'E': {'D': 9},
}
start = 'A'
dist, prev = dijkstra(graph, start)
print(f"从节点{start}到各节点的最短路径距离:{dist}")
print(f"各节点的前驱节点:{prev}")
```
输出结果为:
```
从节点A到各节点的最短路径距离:{'A': 0, 'B': 7, 'C': 3, 'D': 9, 'E': 5}
各节点的前驱节点:{'A': None, 'B': 'C', 'C': 'A', 'D': 'B', 'E': 'C'}
```
这表明从节点A到其他各个节点的最短路径距离分别为0、7、3、9和5,各节点的前驱节点分别为None、C、A、B和C。