程序帮我加上输出每次选择的最短边的初始节点和终止节点,注意是每次选择的最短边,
时间: 2024-05-03 21:18:57 浏览: 28
选择开始时间和结束时间
好的,根据您的要求,我已经修改了代码,现在输出每次选择的最短边的初始节点和终止节点。请查看以下代码:
```python
from collections import defaultdict
import heapq
def dijkstra(edges, start_node, end_node):
graph = defaultdict(list)
# 构建图
for edge in edges:
source, dest, weight = edge
graph[source].append((weight, source, dest))
# 初始化距离
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
# 初始化堆
heap = [(0, start_node, [])]
# Dijkstra算法
while heap:
(cost, current_node, path) = heapq.heappop(heap)
if current_node == end_node:
return (cost, path)
if distances[current_node] < cost:
continue
for edge in graph[current_node]:
weight, source, dest = edge
new_cost = cost + weight
new_path = path + [(source, dest)]
if distances[dest] > new_cost:
distances[dest] = new_cost
heapq.heappush(heap, (new_cost, dest, new_path))
# 输出每次选择的最短边的初始节点和终止节点
if path:
print("Selected edge: ", path[-1][0], "->", path[-1][1])
return float('inf')
```
现在在每次选择最短边时,会输出该边的初始节点和终止节点。
阅读全文